Top Qs
Timeline
Chat
Perspective
Grünbaum–Nash-Williams conjecture
On Hamiltonian cycles in toroidal graphs From Wikipedia, the free encyclopedia
Remove ads
In graph theory, the Grünbaum–Nash-Williams conjecture states that every 4-vertex-connected toroidal graph has a Hamiltonian cycle.[1] It is a generalization of Tutte's theorem on Hamiltonian cycles, according to which every 4-vertex-connected planar graph has a Hamiltonian cycle.[2] An analogous theorem of Thomas and Yu holds for graphs on the projective plane.[3]
For 4-vertex-connected planar and projective planar graphs, more strongly, every edge belongs to a Hamiltonian cycle. However, this stronger property is not true of toroidal graphs. For instance, the Cartesian product of two even cycles, with a diagonal added to one of its quadrilateral faces, is a 4-vertex-connected toroidal graph none of whose Hamiltonian cycles contains the added diagonal.[4][5]
The conjecture was formulated in the early 1970s by Branko Grünbaum[6] and Crispin Nash-Williams.[7] As partial progress toward the conjecture, Robin Thomas and X. Yu proved that every 5-vertex-connected toroidal graph has a Hamiltonian cycle,[8] and (with W. Zang) that every 4-vertex-connected toroidal graph has a Hamiltonian path.[9]
Remove ads
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads