#### Award Date

1-1-2002

#### Degree Type

Thesis

#### Degree Name

Master of Science (MS)

#### Department

Mathematical Sciences

#### First Committee Member

Michelle Schultz

#### Number of Pages

59

#### Abstract

A set {a1, a2,.., an} of positive integers with a 1 < a2 < &cdots; < an is said to be equi-graphical if there exists a graph with exactly ai vertices of degree ai for each i with 1 ≤ i ≤ n. It is known that such a set is equi-graphical if and only if i=1nai is even and an≤i=1n-1 ai2 . This concept is now generalized to the following problem: Given a set S of positive integers and a permutation pi on S, determine when there exists a graph containing exactly ai vertices of degree pi(ai) for each i (1 ≤ i ≤ n). If such a graph exists, then pi is called a graphical permutation; In this paper, the graphical permutations on sets of size four are characterized and using a criterion of Fulkerson, Hoffman, and McAndrew, we show that a permutation pi of S = {a1, a2, .. , an}, where 1 ≤ a1 < a2 < &cdots; < an and such that pi(a n) = an, is graphical if and only if i=1naip ai is even and an≤i=1n-1 aipai .

#### Keywords

Degrees; Equi; Graphical; Graphs; Permutations; Problem; Sets

#### Controlled Subject

Mathematics

#### File Format

#### File Size

1392.64 KB

#### Degree Grantor

University of Nevada, Las Vegas

#### Language

English

#### Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

#### Identifier

https://doi.org/10.25669/naxf-z507

#### Repository Citation

Watson, Michael Lee, "From equi-graphical sets to graphical permutations: A problem of degrees in graphs" (2002). *UNLV Retrospective Theses & Dissertations*. 1409.

https://digitalscholarship.unlv.edu/rtds/1409

COinS