Grünbaum–Nash-Williams conjecture
 |
Unsolved problem in mathematics: Does every 4-vertex-connected toroidal graph have a Hamiltonian cycle? (more unsolved problems in mathematics)
|
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]
References
- ↑ "Chords of longest circuits in locally planar graphs", European Journal of Combinatorics 28 (1): 315–321, 2007, doi:10.1016/j.ejc.2005.07.017
- ↑ "A theorem on planar graphs", Transactions of the American Mathematical Society 82 (1): 99–116, 1956, doi:10.2307/1992980
- ↑ "4-connected projective-planar graphs are Hamiltonian", Journal of Combinatorial Theory, Series B 62 (1): 114–132, 1994, doi:10.1006/jctb.1994.1058
- ↑ Ellingham, M. N.; Marshall, Emily A. (2016), "Criticality of counterexamples to toroidal edge-Hamiltonicity", Graphs and Combinatorics 32 (1): 111–121, doi:10.1007/s00373-015-1542-5
- ↑ "A theorem on paths in planar graphs", Journal of Graph Theory 7 (2): 169–176, 1983, doi:10.1002/jgt.3190070205
- ↑ "Polytopes, graphs, and complexes", Bulletin of the American Mathematical Society 76 (6): 1131–1201, 1970, doi:10.1090/S0002-9904-1970-12601-5
- ↑ "Unexplored and semi-explored territories in graph theory", New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), Academic Press, 1973, pp. 149–186
- ↑ "Five-connected toroidal graphs are Hamiltonian", Journal of Combinatorial Theory, Series B 69 (1): 79–96, 1997, doi:10.1006/jctb.1996.1713
- ↑ "Hamilton paths in toroidal graphs", Journal of Combinatorial Theory, Series B, Series B 94 (2): 214–236, 2005, doi:10.1016/j.jctb.2005.01.002
 |  |
