2024/09/22 by M. N. Ellingham, Joanna A. Ellis-Monaghan, Ellingham, M. N. +1
Computer Science · Engineering · Mathematics · #05C10 (Primary) 05C45 (Secondary) #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2409.14531
openalex publication_date 2024/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a density condition for when, subject to a necessary parity condition, an eulerian graph or digraph may be cellularly embedded in an orientable surface so that it has exactly two faces, each bounded by an euler circuit, one of which may be specified in advance. More generally, suppose that every vertex in an n-vertex eulerian digraph (loops and multiple arcs allowed) has at least (4n+2)/5 neighbors, and specify any decomposition of the arcs into disjoint directed circuits (closed trails). We show that such a digraph has an orientable embedding in which the given circuits are facial walks and there are exactly one or two other faces. This embedding then has maximum genus relative to the given circuits being facial walks. When there is only one other face, it is necessarily bounded by an euler circuit. Consequently, if the numbers of vertices and edges have the same parity, a sufficiently dense digraph D with a given directed euler circuit T has an orientable embedding with exactly two faces, each bounded by an euler circuit, one of which is T. These results for digraphs give analogous results for graphs as immediate corollaries. The main theorem encompasses several special cases in the literature, such as when the digraph is a tournament.