The Heawood graph and $K_{3,3}$ have the property that all of their 2-factors are Hamilton circuits. We call such graphs 2-factor hamiltonian. We prove that if G is a k-regular bipartite 2-factor hamiltonian graph then either G is a circuit or k = 3. Furthermore, we construct an infinite family of cubic bipartite 2-factor hamiltonian graphs based on the Heawood graph and $K_{3,3}$ and conjecture that these are the only such graphs.
2-Factor hamiltonian graphs
FUNK, Martin;LABBATE, Domenico;
2003-01-01
Abstract
The Heawood graph and $K_{3,3}$ have the property that all of their 2-factors are Hamilton circuits. We call such graphs 2-factor hamiltonian. We prove that if G is a k-regular bipartite 2-factor hamiltonian graph then either G is a circuit or k = 3. Furthermore, we construct an infinite family of cubic bipartite 2-factor hamiltonian graphs based on the Heawood graph and $K_{3,3}$ and conjecture that these are the only such graphs.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
