On the degree sequences of dual graphs on surfaces

arXiv2008.00573MaRDI QIDQ6346337FDOQ6346337

Authors: Endre Boros, Vladimir Gurvich, Martin Milanič, Jernej Vičič 

Publication date: 2 August 2020

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 $$ and $$ be their degree sequences. Then, clearly, $su{m}_{i=1}^n{d}_i=su{m}_{j=1}^m{t}_j=2ell$, 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 $$ and $$ 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 $chileq0$.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

This page was built for publication: On the degree sequences of dual graphs on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346337)