From Equi-graphical Sets to Graphical Permutations

Abstract

A set $\{a_1,a_2,\dots ,a_n\}$ of positive integers with $a_1<a_2<\cdots <a_n$ is said to be equi-graphical if there exists a graph with exactly $a_i$ vertices of degree $a_i$ for each $i$ with $1\le i\le n$. It is known that such a set is equi-graphical if and only if $\sum _{i=1}^n{a}_i$ is even and $a_n\le \sum _{i=1}^{n-1}{a}_i^2$. This concept is 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 $a_i$ vertices of degree $\pi (a_i)$ 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=\{a_1,a_2,\dots ,a_n\}$, where $1\le a_1<a_2<\cdots <a_n$ and such that $\pi (a_n)=a_n$, is graphical if and only if $\sum _{i=1}^n{a}_i\pi (a_i)$ is even and $a_n\le \sum _{i=1}^{n-1}{a}_i\pi (a_i)$.