Contents

-

From Equi-graphical Sets to Graphical Permutations

Michelle Schultz1, Michael Watson1
1Department of Mathematical Sciences University of Nevada Las Vegas Las Vegas NV 89154-4020

Abstract

A set {a1,a2,,an} of positive integers with a1<a2<<an is said to be equi-graphical if there exists a graph with exactly ai vertices of degree ai for each i with 1in. It is known that such a set is equi-graphical if and only if i=1nai is even and ani=1n1ai2. This concept is generalized to the following problem: Given a set S of positive integers and a permutation π on S, determine when there exists a graph containing exactly ai vertices of degree π(ai) for each i (1in). If such a graph exists, then π 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 π of S={a1,a2,,an}, where 1a1<a2<<an and such that π(an)=an, is graphical if and only if i=1naiπ(ai) is even and ani=1n1aiπ(ai).