From Equi-graphical Sets to Graphical Permutations

A set \( \{a_1,a_2,\ldots,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 \leq i \leq 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 \leq \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 \leq i \leq 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,\ldots,a_n\} \), where \( 1 \leq 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 \leq \sum_{i=1}^{n-1} a_i\pi(a_i) \).