2013/10/21 by Andrea Jiménez, Jiménez, Andrea, Martin Loebl +1 · 1 citation
Computer Science · Engineering · Mathematics · #05C38 #05C40 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1310.5539
openalex publication_date 2013/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explore the well-known Jaeger's directed cycle double cover conjecture which is equivalent to the assertion that every cubic bridgeless graph has an embedding on a closed orientable surface with no dual loop. We associate each cubic graph G with a novel object H that we call a "hexagon graph"; perfect matchings of H describe all embeddings of G on closed orientable surfaces. The study of hexagon graphs leads us to define a new class of graphs that we call "lean fork-graphs". Fork graphs are cubic bridgeless graphs obtained from a triangle by sequentially connecting fork-type graphs and performing Y-Delta, Delta-Y transformations; lean fork-graphs are fork graphs fulfilling a connectivity property. We prove that Jaeger's conjecture holds for the class of lean fork-graphs. The class of lean fork-graphs is rich; namely, for each cubic bridgeless graph G there is a lean fork-graph containing a subdivision of G as an induced subgraph. Our results establish for the first time, to the best of our knowledge, the validity of Jaeger's conjecture in a broad inductively defined class of graphs.