A Study of Graphical Permutations

Abstract

A permutation $\pi$ on a set of positive integers $\{a_1,a_2,\dots ,a_n\}$ is said to be graphical if there exists a graph containing exactly $a_i$ vertices of degree $\pi (a_i)$ for each $i$ ($1\le i\le n$). It has been shown that for positive integers with $a_1<a_2<\dots <a_n$, if $\pi (a_n)=a_n$, then the permutation $\pi$ is graphical if and only if the sum $\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)$.

We use a criterion of Tripathi and Vijay to provide a new proof of this result and to establish a similar result for permutations $\pi$ such that $\pi (a_{n-1})=a_n$. We prove that such a permutation is graphical if and only if the sum $\sum _{i=1}^n{a}_i\pi (a_i)$ is even and $a_n{a}_{n-1}\le a_{n-1}(a_{n-1}–1)+\sum _{i\ne n-1}{a}_i\pi (a_i)$. We also consider permutations such that $\pi (a_n)=a_{n-1}$ and, more generally, those such that $\pi (a_n)=a_{n-j}$ for some $j$ ($1<j<n$).