Let $pi_1=(d_1^{(1)}, ldots,d_n^{(1)})$ and $pi_2=(d_1^{(2)},ldots,d_n^{(2)})$ be graphic sequences. We say they emph{pack} if there exist edge-disjoint realizations $G_1$ and $G_2$ of $pi_1$ and $pi_2$, respectively, on vertex set ${v_1,dots,v_n}$ such that for $jin{1,2}$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $iin{1,ldots,n}$. In this case, we say that $(G_1,G_2)$ is a $(pi_1,pi_2)$-textit{packing}. A clear necessary condition for graphic sequences $pi_1$ and $pi_2$ to pack is that $pi_1+pi_2$, their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is $NP$- complete. S.~Kundu proved in 1973 that if $pi_2$ is almost regular, that is each element is from ${k-1, k}$, then $pi_1$ and $pi_2$ pack if and only if $pi_1+pi_2$ is graphic. In this paper we will consider graphic sequences $pi$ with the property that $pi+mathbf{1}$ is graphic. By Kundus theorem, the sequences $pi$ and $mathbf{1}$ pack, and there exist edge-disjoint realizations $G$ and $mathcal{I}$, where $mathcal{I}$ is a 1-factor. We call such a $(pi,mathbf{1})$ packing a {em Kundu realization}. Assume that $pi$ is a graphic sequence, in which each term is at most $n/24$, that packs with $mathbf{1}$. This paper contains two results. On one hand, any two Kundu realizations of the degree sequence $pi+mathbf{1}$ can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of $pi+mathbf{1}$.
Download