From equi-graphical sets to graphical permutations: A problem of degrees in graphs

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 &le; i &le; n. It is known that such a set is equi-graphical if and only if i=1nai is even and an&le;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 &le; i &le; 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 &le; a1 < a2 < &cdots; < an and such that pi(a n) = an, is graphical if and only if i=1naip ai is even and an&le;i=1n-1 aipai .

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Mathematical Sciences

Grantor dc:publisher

University of Nevada, Las Vegas

Year

2002

Author dc:creator

• Watson, Michael Lee

Contributors dc:contributor

• Michelle Schultz

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/1409

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-2408