Grünbaum–Nash-Williams conjecture
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
[edit]- ^ Kawarabayashi, Ken-ichi; Niu, Jianbing; Zhang, Cun-Quan (2007), "Chords of longest circuits in locally planar graphs", European Journal of Combinatorics, 28 (1): 315–321, doi:10.1016/j.ejc.2005.07.017, MR 2261821
- ^ Tutte, W. T. (1956), "A theorem on planar graphs", Transactions of the American Mathematical Society, 82 (1): 99–116, doi:10.2307/1992980, JSTOR 1992980, MR 0081471
- ^ Thomas, Robin; Yu, Xingxing (1994), "4-connected projective-planar graphs are Hamiltonian", Journal of Combinatorial Theory, Series B, 62 (1): 114–132, doi:10.1006/jctb.1994.1058, MR 1290634
- ^ 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, MR 3436953
- ^ Thomassen, Carsten (1983), "A theorem on paths in planar graphs", Journal of Graph Theory, 7 (2): 169–176, doi:10.1002/jgt.3190070205, MR 0698698
- ^ Grünbaum, Branko (1970), "Polytopes, graphs, and complexes", Bulletin of the American Mathematical Society, 76 (6): 1131–1201, doi:10.1090/S0002-9904-1970-12601-5, MR 0266050
- ^ Nash-Williams, C. St. J. A. (1973), "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, pp. 149–186, MR 0387097
- ^ Thomas, Robin; Yu, Xingxing (1997), "Five-connected toroidal graphs are Hamiltonian", Journal of Combinatorial Theory, Series B, 69 (1): 79–96, doi:10.1006/jctb.1996.1713, MR 1426752
- ^ Thomas, Robin; Yu, Xingxing; Zang, Wenan (2005), "Hamilton paths in toroidal graphs", Journal of Combinatorial Theory, Series B, Series B, 94 (2): 214–236, doi:10.1016/j.jctb.2005.01.002, MR 2145513