Premium
Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
Author(s) -
Fleischner Herbert
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180503
Subject(s) - mathematics , eulerian path , cycle basis , combinatorics , uniqueness , hamiltonian path , pancyclic graph , hamiltonian (control theory) , indifference graph , discrete mathematics , chordal graph , graph , 1 planar graph , pure mathematics , line graph , graph power , lagrangian , mathematical analysis , mathematical optimization
We construct 3‐regular (cubic) graphs G that have a dominating cycle C such that no other cycle C 1 of G satisfies V(C) ⊆ V ( C 1 ). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these constructions are considerations on the uniqueness of a cycle decomposition compatible with a given eulerian trail in some eulerian graph.