{
  "id": "2008.00573",
  "version": "v1",
  "published": "2020-08-02T22:08:10.000Z",
  "updated": "2020-08-02T22:08:10.000Z",
  "title": "On the degree sequences of dual graphs on surfaces",
  "authors": [
    "Endre Boros",
    "Vladimir Gurvich",
    "Martin Milanič",
    "Jernej Vičič"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given two graphs $G$ and $G^*$ with a one-to-one correspondence between their edges, when do $G$ and $G^*$ form a pair of dual graphs realizing the vertices and countries of a map embedded in a surface? A criterion was obtained by Jack Edmonds in 1965. Furthermore, let $\\boldsymbol{d}=(d_1,\\ldots,d_n)$ and $\\boldsymbol{t}=(t_1,\\ldots,t_m)$ be their degree sequences. Then, clearly, $\\sum_{i=1}^n d_i = \\sum_{j=1}^m t_j = 2\\ell$, where $\\ell$ is the number of edges in each of the two graphs, and $\\chi = n - \\ell + m$ is the Euler characteristic of the surface. Which sequences $\\boldsymbol{d}$ and $\\boldsymbol{t}$ satisfying these conditions still cannot be realized as the degree sequences? We make use of Edmonds' criterion to obtain several infinite series of exceptions for the sphere, $\\chi = 2$, and projective plane, $\\chi = 1$. We conjecture that there exist no exceptions for $\\chi \\leq 0$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-02T22:08:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C07",
      "05C45",
      "05C62"
    ],
    "keywords": [
      "degree sequences",
      "one-to-one correspondence",
      "infinite series",
      "euler characteristic",
      "jack edmonds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}