{
  "id": "1709.07628",
  "version": "v1",
  "published": "2017-09-22T08:20:18.000Z",
  "updated": "2017-09-22T08:20:18.000Z",
  "title": "Navigating Between Packings of Graphic Sequences",
  "authors": [
    "Peter L. Erdos",
    "Michael Ferrara",
    "Stephen G. Hartke"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 $j\\in\\{1,2\\}$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $i\\in\\{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 Kundu's 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}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-22T08:20:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07"
    ],
    "keywords": [
      "graphic sequence",
      "kundu realization",
      "edge-disjoint realizations",
      "clear necessary condition",
      "navigating"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}