article

On some intriguing problems in hamiltonian graph theory: a survey

Author:

H. J. BroersmaAuthors Info & Claims

Discrete Mathematics, Volume 251, Issue 1

Pages 47 - 69

https://doi.org/10.1016/S0012-365X(01)00325-9

Published: 28 May 2002 Publication History

Abstract

We survey results and open problems in hamiltonian graph theory centered around three themes: regular graphs, t-tough graphs, and claw-free graphs.

References

[1]

{1} D. Bauer, H.J. Broersma, J. van den Heuvel, H.J. Veldman, On hamiltonian properties of 2-tough graphs, J. Graph Theory 18 (1994) 539-543.

Digital Library

Google Scholar

[2]

{2} D. Bauer, H.J. Broersma, J. van den Heuvel, H.J. Veldman, Long cycles in graphs with prescribed toughness and minimum degree, Discrete Math. 141 (1995) 1-10.

Crossref

Google Scholar

[3]

{3} D. Bauer, H.J. Broersma, H.J. Veldman, Not every 2-tough graph is hamiltonian, Discrete Appl. Math. 99 (2000) 317-321.

Digital Library

Google Scholar

[4]

{4} D. Bauer, G.Y. Katona, D. Kratsch, H.J. Veldman, Chordality and 2-factors in tough graphs, Discrete Appl. Math. 99 (2000) 323-329.

Digital Library

Google Scholar

[5]

{5} D. Bauer, E. Schmeichel, Toughness, minimum degree, and the existence of 2-factors, J. Graph Theory 18 (1994) 241-256.

Digital Library

Google Scholar

[6]

{6} K. Baxter, The Hopping Lemma, MSc Thesis, University of Waterloo, 1992.

Google Scholar

[7]

{7} J.C. Bermond, Hamiltonian graphs, in: L. Beineke, R.J. Wilson (Eds.), Selected Topics in Graph Theory, Academic Press, London and New York, 1978, pp. 127-167.

Google Scholar

[8]

{8} J.C. Bermond, C. Thomassen, Cycles in digraphs---a survey, J. Graph Theory 5 (1981) 1-43.

Crossref

Google Scholar

[9]

{9} A.A. Bertossi, The edge hamiltonian path problem is NP-complete, Inform. Process. Lett. 13 (1981) 157-159.

Crossref

Google Scholar

[10]

{10} T. Böhme, J. Harant, M. Tkác, More than one tough chordal planar graphs are hamiltonian, J. Graph Theory 32 (1999) 405-410.

Digital Library

Google Scholar

[11]

{11} J.A. Bondy, Hamilton cycles in graphs and digraphs, Congr. Numer. 21 (1978) 3-28.

Google Scholar

[12]

{12} J.A. Bondy, Basic graph theory, in: M. Grötschel, L. Lovász, R.L. Graham (Eds.), Handbook of Combinatorics, North-Holland, Amsterdam, 1995, pp. 3-110.

Crossref

Google Scholar

[13]

{13} J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135.

Digital Library

Google Scholar

[14]

{14} J.A. Bondy, M. Kouider, Hamilton cycles in regular 2-connected graphs, J. Combin. Theory B 44 (1988) 177-186.

Crossref

Google Scholar

[15]

{15} J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.

Crossref

Google Scholar

[16]

{16} H.J. Broersma, J. van den Heuvel, B. Jackson, H.J. Veldman, Hamiltonicity of regular 2-connected graphs, J. Graph Theory 22 (1996) 105-124.

Digital Library

Google Scholar

[17]

{17} H.J. Broersma, J. van den Heuvel, H.A. Jung, H.J. Veldman, Cycles containing all vertices of maximum degree, J. Graph Theory 17 (1993) 373-385.

Digital Library

Google Scholar

[18]

{18} H.J. Broersma, J. van den Heuvel, H.J. Veldman, A generalization of Ore's Theorem involving neighborhood unions, Discrete Math. 122 (1993) 37-49.

Digital Library

Google Scholar

[19]

{19} H.J. Broersma, M. Kriesell, Z. Ryjácek, On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136.

Digital Library

Google Scholar

[20]

{20} H.J. Broersma, S. van der Laag, Long cycles in 2-connected and 3-connected claw-free graphs, Working paper.

Google Scholar

[21]

{21} H.J. Broersma, Z. Ryjácek, I. Schiermeyer, Closure concepts---a survey, Graphs and Combin. 16 (2000) 1748.

Crossref

Google Scholar

[22]

{22} P.A. Catlin, A reduction method to find spanning eulerian subgraphs, J. Graph Theory 12 (1988) 29-44.

Crossref

Google Scholar

[23]

{23} G. Chen, M.S. Jacobson, A. Kézdy, J. Lehel, Tough enough chordal graphs are hamiltonian, Networks 31 (1998) 29-38.

Crossref

Google Scholar

[24]

{24} V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973) 215-228.

Digital Library

Google Scholar

[25]

{25} V. Chvátal, Hamiltonian cycles, Chapter 11 in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem, Wiley, New York, 1985.

Google Scholar

[26]

{26} G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952) 69-81.

Crossref

Google Scholar

[27]

{27} H. Enomoto, B. Jackson, P. Katerinis, A. Saito, Toughness and the existence of k-factors, J. Graph Theory 9 (1985) 87-95.

Crossref

Google Scholar

[28]

{28} G. Fan, personal communication.

Google Scholar

[29]

{29} R.J. Faudree, E. Flandrin, Z. Ryjácek, Claw-free graphs---a survey, Discrete Math. 164 (1997) 87-147.

Digital Library

Google Scholar

[30]

{30} O. Favaron, E. Flandrin, H. Li, Z. Ryjácek, Clique covering and degree conditions for hamiltonicity in claw-free graphs, preprint, 1997.

Google Scholar

[31]

{31} O. Favaron, P. Fraisse, Hamiltonicity and minimum degree in 3-connected claw-free graphs, preprint, 1999.

Google Scholar

[32]

{32} H. Fleischner, The square of every 2-connected graph is hamiltonian, J. Combin. Theory (B) 16 (1974) 29-34.

Crossref

Google Scholar

[33]

{33} H. Fleischner, B. Jackson, A note concerning some conjectures on cyclically 4-edge connected 3-regular graphs, Ann. Discrete Math. 41 (1989) 171-178.

Crossref

Google Scholar

[34]

{34} R.J. Gould, Updating the hamiltonian problem---a survey, J. Graph Theory 15 (1991) 121-157.

Digital Library

Google Scholar

[35]

{35} R. Häggkvist, On the structure of non-hamiltonian graphs I, Combin. Probab. Comput. 1 (1992) 27-34.

Crossref

Google Scholar

[36]

{36} F. Harary, C.St.J.A. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701-710.

Crossref

Google Scholar

[37]

{37} J. van den Heuvel, Degree and toughness conditions for cycles in graphs, Ph.D. Thesis, University of Twente, 1993.

Google Scholar

[38]

{38}J. van den Heuvel, personal communication.

Google Scholar

[39]

{39} F. Hilbig, Kantenstrukturen in nichthamiltonschen Graphen, Ph.D. Thesis, Technische Universität Berlin, 1986.

Google Scholar

[40]

{40} D.A. Holton, B.D. McKay, M.D. Plummer, C. Thomassen, A nine point theorem for 3-connected graphs, Combinatorica 2 (1982) 53-62.

Crossref

Google Scholar

[41]

{41} S. Ishizuka, Closure, path factors and path coverings in claw-free graphs, preprint, 1998.

Google Scholar

[42]

{42} B. Jackson, Hamilton cycles in regular 2-connected graphs, J. Combin. Theory B 29 (1980) 27-46.

Crossref

Google Scholar

[43]

{43} B. Jackson, Hamilton cycles in 7-connected line graphs, preprint, 1989.

Google Scholar

[44]

{44} B. Jackson, Concerning the circumference of certain families of graphs, in: H.J. Broersma, J. van den Heuvel, H.J. Veldman (Eds.), Updated Contributions to the Twente Workshop on Hamiltonian Graph Theory, Memorandum No. 1076, University of Twente, Enschede, 1992, pp. 87-94.

Google Scholar

[45]

{45} B. Jackson, personal communication.

Google Scholar

[46]

{46} B. Jackson, H. Li, Y. Zhu, Dominating cycles in regular 3-counected graphs, Discrete Math. 102 (1991) 163-176.

Digital Library

Google Scholar

[47]

{47} B. Jackson, N.C. Wormald, k-Walks of graphs, Austral. J. Combin. 2 (1990) 135-146.

Google Scholar

[48]

{48} F. Jaeger, A note on subeulerian graphs, J. Graph Theory 3 (1979) 91-93.

Crossref

Google Scholar

[49]

{49} H.A. Jung, On maximal circuits in finite graphs, Ann. Discrete Math. 3 (1987) 129-144.

Crossref

Google Scholar

[50]

{50} M. Kochol, Sublinear defect principle in graph theory, manuscript, 1999.

Google Scholar

[51]

{51} D. Kratsch, personal communication.

Google Scholar

[52]

{52} D. Kratsch, J. Lehel, H. Müller, Toughness, hamiltonicity and split graphs, Discrete Math. 150 (1996) 231-245.

Crossref

Google Scholar

[53]

{53} M. Kriesell, All 4-connected line graphs of claw-free graphs are hamiltonian-connected, preprint, 1998.

Google Scholar

[54]

{54} E.J. Kuipers, H.J. Veldman, Recognizing claw-free hamiltonian graphs with large minimum degree, preprint, 1998.

Google Scholar

[55]

{55} S. Kundu, Bounds on the number of disjoint spanning trees, J. Combin. Theory B 17 (1974) 199-203.

Crossref

Google Scholar

[56]

{56} H. Li, A note on hamiltonian claw-free graphs, Rapport de Recherche 1022, Univ. Paris-Sud, Orsay, France, 1996.

Google Scholar

[57]

{57} X. Liu, D. Wang, A new generalization of Ore's Theorem involving neighborhood unions, Systems Sci. Math. Sci. 9 (1996) 182-192.

Google Scholar

[58]

{58} X. Liu, L. Zhang, Y. Zhu, Distance, neighborhood unions and hamiltonian properties in graphs, in: Y. Alavi, D.R. Lick, J. Liu (Eds.), Combinatorics, Graph Theory, Algorithms and Applications, Proceedings of the Third China-USA International Conference, Beijing, June 1-5, 1993, World Scientific Publ. Co., Inc., River Edge, NJ, 1994, pp. 255-268.

Google Scholar

[59]

{59} M.M. Matthews, D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984) 139-146.

Crossref

Google Scholar

[60]

{60} M.M. Matthews, D.P. Sumner, Longest paths and cycles in K1,3-free graphs, J. Graph Theory 9 (1985) 269-277.

Crossref

Google Scholar

[61]

{61} Min Aung, Circumference of a regular graph, J. Graph Theory 13 (1989) 149-155.

Crossref

Google Scholar

[62]

{62} C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961) 445-450.

Crossref

Google Scholar

[63]

{63} D.J. Oberly, D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is hamiltonian, J. Graph Theory 3 (1979) 351-356.

Crossref

Google Scholar

[64]

{64} O. Ore, Note on hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55.

Crossref

Google Scholar

[65]

{65} Z. Ryjácek, On a closure concept in claw-free graphs, J. Combin. Theory B 70 (1997) 217-224.

Digital Library

Google Scholar

[66]

{66} Z. Ryjácek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117.

Digital Library

Google Scholar

[67]

{67} C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324.

Crossref

Google Scholar

[68]

{68} C. Thomassen, On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996) 437-442.

Crossref

Google Scholar

[69]

{69} W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116.

Crossref

Google Scholar

[70]

{70} W.T. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961) 221-230.

Crossref

Google Scholar

[71]

{71} H.J. Veldman, Existence of Dλ-cycles and Dλ-paths, Discrete Math. 44 (1983) 309-316.

Digital Library

Google Scholar

[72]

{72} H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239.

Digital Library

Google Scholar

[73]

{73} M.E. Watkins, D.M. Mesner, Cycles and connectivity in graphs, Can. J. Math. 19 (1967) 1319-1328.

Crossref

Google Scholar

[74]

{74} D.R. Woodall, The binding number of a graph and its Anderson number, J. Combin. Theory B 15 (1973) 225-255.

Crossref

Google Scholar

[75]

{75} S. Zhan, On hamiltonian line graphs and connectivity, Discrete Math. 89 (1991) 89-95.

Digital Library

Google Scholar

[76]

{76} Y. Zhu, H. Li, Hamilton cycles in regular 3-connected graphs, Discrete Math. 110 (1992) 229-249.

Digital Library

Google Scholar

[77]

{77} Y. Zhu, Z. Liu, Z. Yu, 2-Connected k-regular graphs on at most 3k + 3 vertices to be hamiltonian, J. Systems Sci. Math. Sci. 6 (1) (1986) 36-49; (2) (1986) 136-145.

Google Scholar

Cited By

View all

Ma XVumar E(2018)Neighborhood Union Conditions for Hamiltonicity of P3-Dominated GraphsGraphs and Combinatorics10.1007/s00373-013-1354-430:6(1499-1511)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00373-013-1354-4
Ozeki K(2018)Hamiltonicity of Graphs on Surfaces in Terms of Toughness and Scattering Number – A SurveyDiscrete and Computational Geometry, Graphs, and Games10.1007/978-3-030-90048-9_7(74-95)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-90048-9_7
Chiba SFuruya MTsuchiya S(2015)Forbidden pairs and the existence of a dominating cycleDiscrete Mathematics10.1016/j.disc.2015.06.018338:12(2442-2452)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.06.018

Index Terms

On some intriguing problems in hamiltonian graph theory: a survey
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems

Recommendations

How Many Conjectures Can You Stand? A Survey

We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting ...
Toughness and hamiltonicity in k-trees

We consider toughness conditions that guarantee the existence of a hamiltonian cycle in k-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are hamiltonian, and by a result of Bauer et al. there exist ...
On 3-connected hamiltonian line graphs

Thomassen conjectured that every 4-connected line graph is hamiltonian. It has been proved that every 4-connected line graph of a claw-free graph, or an almost claw-free graph, or a quasi-claw-free graph, is hamiltonian. In 1998, Ainouche et al. [2] ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Discrete Mathematics Volume 251, Issue 1

28 May 2002

172 pages

ISSN:0012-365X

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 28 May 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ma XVumar E(2018)Neighborhood Union Conditions for Hamiltonicity of P3-Dominated GraphsGraphs and Combinatorics10.1007/s00373-013-1354-430:6(1499-1511)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00373-013-1354-4
Ozeki K(2018)Hamiltonicity of Graphs on Surfaces in Terms of Toughness and Scattering Number – A SurveyDiscrete and Computational Geometry, Graphs, and Games10.1007/978-3-030-90048-9_7(74-95)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-90048-9_7
Chiba SFuruya MTsuchiya S(2015)Forbidden pairs and the existence of a dominating cycleDiscrete Mathematics10.1016/j.disc.2015.06.018338:12(2442-2452)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.06.018

Abstract

References

Cited By

Index Terms

Recommendations

How Many Conjectures Can You Stand? A Survey

Toughness and hamiltonicity in k-trees

On 3-connected hamiltonian line graphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations