2015/08/08 by Simona Bonvicini, Bonvicini, Simona, Tomaž Pisanski +1 · 1 citation
Engineering · #05C15 #05C25 #05C45 #05C60 #05C70 #05C76 #55R10 #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1508.01865
openalex publication_date 2015/08/08 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
We give a necessary and sufficient condition for a cubic graph to be\nHamiltonian by analyzing Eulerian tours in certain spanning subgraphs of the\nquartic graph associated with the cubic graph by 1-factor contraction. This\ncorrespondence is most useful in the case when it induces a blue and red\n2-factorization of the associated quartic graph. We use this condition to\ncharacterize the Hamiltonian I-graphs, a further generalization of generalized\nPetersen graphs. The characterization of Hamiltonian I-graphs follows from the\nfact that one can choose a 1-factor in any I-graph in such a way that the\ncorresponding associated quartic graph is a graph bundle having a cycle graph\nas base graph and a fiber and the fundamental factorization of graph bundles\nplaying the role of blue and red factorization. The techniques that we develop\nallow us to represent Cayley multigraphs of degree 4, that are associated to\nabelian groups, as graph bundles. Moreover, we can find a family of connected\ncubic (multi)graphs that contains the family of connected I-graphs as a\nsubfamily.\n