×

zbMATH — the first resource for mathematics

Updating the Hamiltonian problem – a survey. (English) Zbl 0746.05039
This paper is a survey of the results on Hamiltonian paths and cycles in undirected graphs obtained since the late 1970s. Dirac’s classical theorem has many generalizations involving degrees, neighborhood intersection, distance, toughness and other parameters. Also, results on random graphs, forbidden subgraphs, algorithms, the number of Hamiltonian cycles, Hamiltonian decompositions, and highly symmetric graphs are reviewed.

MSC:
05C45 Eulerian and Hamiltonian graphs
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agano, J. Graph Theory 4 pp 315– (1980)
[2] Ainouche, J. London Math Soc. (2) 32 pp 385– (1985)
[3] Ainouche, Discrete Applied Math 17 pp 213– (1987)
[4] Hamiltonian cycles in vertex-transitive graphs of order 2p. Ulilitas Math. (1979), 131–139.
[5] Alspach, J. Combinat. Theory Ser. B. 34 pp 293– (1983)
[6] Alspach, J. Combinat. Theory B 31 pp 225– (1981)
[7] , , and , Covering the vertices of a simple graph with given connectivity and stability number. International Conference on Convexity and Graph Theory, Israel (1980).
[8] Angluin, J. Comput. System Sci. 18 pp 155– (1979)
[9] Asano, Discrete Appl. Math 7 pp 1– (1984)
[10] Asratyan, Mat. Zamethki 35 pp 55– (1984)
[11] and , On a stability of some properties of a graph. Preprint.
[12] Aubert, Discrete Math. 38 pp 7– (1982)
[13] Problem 17, unsolved problems. Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, July (1979).
[14] Babai, J. Graph Theory 3 pp 301– (1979)
[15] , and , On generalizing a theorem of Jung. Preprint. · Zbl 0843.05071
[16] Bauer, J. Combinat. Theory B 47 pp 237– (1989)
[17] Bauer, Discrete Math.
[18] Bauer, Discrete Math. 79 pp 59– (1990)
[19] , and , Some recent results on long cycles in tough graphs. Proceedings of the Sixth International Conference on the Theory and Applications of Graphs, to appear. · Zbl 0840.05049
[20] Benhocine, J. Graph Theory 10 pp 411– (1986)
[21] Benhocine, Discrete Math. 66 pp 21– (1987)
[22] Benhocine, J. Combinat. Theory B 42 pp 167– (1987)
[23] Hamiltonian graphs. Selected Topics in Graph Theory. Academic Press, London (1978).
[24] Bermond, J. Graph Theory 5 pp 1– (1981)
[25] Bigulke, Monatsh. Math. 88 pp 195– (1979)
[26] Bollobás, Eur. J. Combinat. 4 pp 99– (1983) · Zbl 0513.05048
[27] Bollobás, Combinatorica 2 pp 223– (1982)
[28] Random Graphs. Academic Press, London (1985).
[29] Bollobás, Proceedings of the ACM Symposium on the Theory of Computing 17 pp 430– (1985)
[30] Bollobás, J. Combinat. Theory B
[31] Bondy, Congr. Numer. 21 pp 3– (1978)
[32] Longest paths and cycles in graphs of high degree. Research Report CORR 80–16, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada (1980).
[33] Bondy, Discrete Math. 15 pp 111– (1976)
[34] Bondy, Discrete Math. 67 pp 205– (1987)
[35] Bondy, Aequationes Math. 22 pp 41– (1981)
[36] Bondy, J. Combinat. Theory B 20 pp 41– (1976)
[37] Bondy, J. Combinat. Theory B 44 pp 177– (1988)
[38] Bondy, Combinatorica 1 pp 137– (1981)
[39] and , Graph Theory with Applications. Macmillan & Co., London (1976). · Zbl 1226.05083
[40] Hamiltonian lines in cubic graphs. Theory of Graphs (International Symposium, Rome, 1966), Gordon and Breech, New York (1967) 35–46.
[41] and , Restrictions on induced subgraphs ensuring hamiltonicity or pancyclicity of K1,3-free graphs. Preprint. · Zbl 0723.05082
[42] Brualdi, J. Graph Theory 5 pp 307– (1981)
[43] Castagna, Pacific J. Math. 40 pp 53– (1972) · Zbl 0236.05106
[44] and , Graphs and Digraphs. Wadsworth & Brooks/Cole, Belmont CA (1986).
[45] Chen, J. Combinat. Theory B 42 pp 257– (1987)
[46] Chvátal, Discrete Math. 5 pp 215– (1973)
[47] Chvátal, Discrete Math. 2 pp 111– (1972)
[48] Clark, Congr. Numer. 47 pp 189– (1985)
[49] Clark, Ars Combinat. 15 pp 131– (1983)
[50] Cooper, J. Graph Theory 13 pp 719– (1989)
[51] , , and , A survey of graphs hamiltonian-connected from a vertex. Preprint. · Zbl 0841.05065
[52] Hamilton cycles in bipartite reflective Kneser graphs. Preprint. · Zbl 0659.05063
[53] Dirac, Proc. London Math. Soc. 2 pp 69– (1952)
[54] , and , Forbidden subgraphs and the Hamiltonian theme. Theory and Applications of Graphs (Kalamazoo, Michigan, 1980), Wiley, New York (1981) 297–316.
[55] Duffus, J. Combinat. Theory B
[56] , and , Cycles and paths through specified vertices in k-connected graphs. Preprint. · Zbl 0666.05044
[57] Ellingham, J. Combinat. Theory Ser. B 34 pp 350– (1983)
[58] Enomoto, J. Graph Theory 9 pp 87– (1985)
[59] Fan, J. Combinat. Theory Ser. B 37 pp 221– (1984)
[60] Faudree, Colloq. Math. Societ. Janos Bolyai 52 pp 227– (1987)
[61] Faudree, Discrete Math.
[62] Faudree, J. Combinat. Theory B 46 pp 1– (1989)
[63] , and , Hamiltonian properties and adjacency conditions in K1,3-free graphs. Proceedings of the 6th International Conference on Theory and Applications of Graphs, Kalamazoo, 1988, to appear.
[64] Faudree, Congr. Numer. 59 pp 55– (1987)
[65] , and , Edge disjoint hamiltonian cycles. Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Michigan, 1984), Wiley–Interscience, New York (1985) 231–249.
[66] Fenner, Discrete Math. 45 pp 301– (1983)
[67] Fenner, J. Combinat. Theory B 37 pp 103– (1984)
[68] , and , Hamiltonism, degree sums and neighborhood intersections. Preprint. · Zbl 0746.05038
[69] and , Hamiltonism and claws. Report de Recherehe no. 398, Universite de Paris-Sud, Centre d’Orsay (1988).
[70] and , Hamiltonism and neighborhood intersections. Report de Recherehe no. 406, Universite de Paris-Sud, Centre d’Orsay (1988).
[71] Fleischner, J. Combinat. Theory B 16 pp 29– (1974)
[72] Fleischner, Monatsh. Math. 82 pp 125– (1976)
[73] D{\(\lambda\)}-cycles and their applications for Hamiltonian graphs. Preprint.
[74] Fraisse, J. Graph Theory 10 pp 405– (1986)
[75] Frieze, J. Combinat. Theory B 44 pp 230– (1988)
[76] Frieze, Eur. J. Combinat. 6 pp 327– (1985) · Zbl 0592.05051
[77] Goodman, J. Combinat. Theory B 16 pp 175– (1974)
[78] Traceability in graphs. Doctoral thesis, Western Michigan University (1979).
[79] Gould, Discrete Math. 42 pp 189– (1982)
[80] Gould, J. Graph Theory 8 pp 147– (1984)
[81] and , Neighborhood intersections and a generalization of Ore’s theorem. Proceedings of the 2nd International Conference in Graph Theory, Combinatorics, Algorithms, and Applications, San Francisco, July, 1989, to appear.
[82] Grinberg, Latvian Math. Yearbook 4 pp 51– (1968)
[83] Gurevich, SIAM J. Comput. 16 pp 486– (1987)
[84] On f-Hamiltonian graphs. Graph Theory and Related Topics, Academic Press, New York (1979) 219–231.
[85] Häggkvist, Discrete Math. 41 pp 29– (1982)
[86] Häggkvist, J. Combinat. Theory B 30 pp 118– (1981)
[87] Hakimi, J. Combinat. Theory B 44 (1988)
[88] Hakimi, J. Graph Theory 3 pp 365– (1979)
[89] Harary, Can. Math. Bull. 8 pp 701– (1965) · Zbl 0136.44704
[90] Heinrich, J. Austral. Math. Soc. A 26 pp 89– (1978)
[91] Hendry, J. Graph Theory 9 pp 535– (1985)
[92] Holton, J. Combinat. Theory Ser. B 38 pp 279– (1985)
[93] Horak, Math. Slovaca 29 pp 43– (1979)
[94] Jackson, J. London Math. Soc. (2) 19 pp 13– (1979)
[95] Jackson, J. Combinat. Theory B 29 pp 27– (1980)
[96] Jackson, J. Combinat. Theory B 43 pp 245– (1987)
[97] Jackson, Ars Combinat. 25 pp 39– (1988)
[98] Jung, Ann. Discrete Math. 3 pp 129– (1978)
[99] Jung, Arch. Math. (Basel) 39 pp 383– (1982) · Zbl 0495.05042
[100] The probabilistic analysis of some combinatorial search algorithms. Algorithms and Complexity: New Directions and Recent Results. Academic Press, New York (1976) 1–19.
[101] Kierstead, Order 5 pp 163– (1988)
[102] Komlos, Discrete Math. 43 pp 55– (1983)
[103] Korshunov, Soviet Mat. Dokl. 17 pp 760– (1976)
[104] Korshunov, Metody Diskr. Anal. Teoriy Upr. Syst. Sb. Trudov Novosibirsk 31 pp 17– (1977)
[105] Lai, J. Graph Theory 12 pp 11– (1988)
[106] Lai, Discrete Math. 69 pp 43– (1988)
[107] , , and , The Traveling Salesman Problem. Wiley–Interscience Series, New York (1986).
[108] Neighborhood unions and graphical properties. Proceedings of the 6th International Conference on the Theory and Application of Graphs (Kalamazoo, 1988), to appear.
[109] and , Edge-disjoint Hamilton cycles in graphs. Proceedings of the 1st China-USA Conference, to appear. · Zbl 0794.05071
[110] Lindquester, J. Graph Theory 13 pp 335– (1989)
[111] Lipman, Discrete Math. 54 pp 15– (1985)
[112] Locke, Combinatorica 5 pp 149– (1985)
[113] Lovász, J. Combinat. Theory A 25 pp 319– (1978)
[114] Lovász, 5. Period. Math. Hungar. 4 pp 82– (1974)
[115] Combinatorial Problems and Exercises. North Holland, Amsterdam (1979), Section 6.67.
[116] Combinatorial Structures and Their Applications. Gordon and Breach, London (1970) Problem 11.
[117] Marusic, 5p. Discrete Math. 42 pp 227– (1982)
[118] Marusic, p. Discrete Math. 43 pp 91– (1983)
[119] Mather, J. Combinat. Theory B 20 pp 62– (1976)
[120] Matthews, J. Graph Theory 8 pp 139– (1984)
[121] Matthews, J. Graph Theory 9 pp 269– (1985)
[122] McDiarmid, Adv. Appl. Probab. 13 pp 40– (1981)
[123] McDiarmid, Adv. Appl. Probab. 15 pp 149– (1983)
[124] and , Pancyclic and bypancyclic graphs–A survey. Graphs and Applications (Boulder, Colorado, 1982). Wiley–Interscience, New York (1985) 271–287.
[125] Meredith, J. Combinat. Theory B. 15 pp 161– (1973)
[126] Molluzzo, Ann. NY Acd. Sci. 319 pp 402– (1979)
[127] Moon, J. Combinat. Theory B 37 pp 173– (1984)
[128] Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. Studies in Pure Mathematics, Academic Press, London (1971) 157–183.
[129] Nebesky, Casopi Pest. Mat. 110 pp 294– (1985)
[130] An estimate of the number of Hamiltonian cycles in a multigraph. Recent Advances in Graph Theory (Proceedings of the Second Czechoslovak Symposium, Prague, 1974). Academia, Prague (1975) 431–438.
[131] Oberly, J. Graph Theory 3 pp 351– (1979)
[132] Ore, Am. Math. Month. 67 pp 55– (1960)
[133] Owens, J. Combinat. Theory B 28 pp 263– (1980)
[134] Paoli, Discrete Math. 52 pp 91– (1984)
[135] Pósa, Magyar Tud. Akad. Mat. Kutató Int. Közl. 1 pp 225– (1962)
[136] Pósa, Discrete Math. 14 pp 359– (1976)
[137] Richmond, Ann. Discrete Math. 27 pp 141– (1985)
[138] Riha, J. Combinat. Theory B
[139] Graphs with girth, valency, and connectivity constraints. Ph.D. thesis, University of Waterloo, Ontario (1968).
[140] and , Almost all bipartite cubic graphs are hamiltonian. Preprint.
[141] Schiermeyer, Ars Combinat. 25B pp 55– (1988)
[142] A strong closure concept for Hamiltonian graphs. Preprint.
[143] Serdjukov, Upravljaemye Sistemy 19 pp 57– (1979)
[144] Shamir, Combinatorica 3 pp 123– (1983)
[145] Sheehan, J. Graph Theory 1 pp 37– (1977)
[146] Sheehan, Glasgow Math. J. 18 pp 35– (1977)
[147] Sharp sufficient conditions for hamiltonian cycles in tough graphs. Preprint. · Zbl 0715.05046
[148] Sloane, J. Combinat. Theory 6 pp 311– (1969)
[149] Teichert, Elektron. Infortnatsverab. Kybernet 19 pp 611– (1983)
[150] Teichert, Elektron. Informationsverarb. Kybernet. 19 pp 67– (1983)
[151] Teichert, Elektron. Informationsverarb. Kybernet 19 pp 345– (1983)
[152] Teichert, Elektron. Informationsverarb. Kybernet 18 pp 639– (1982)
[153] Thomason, Ann. Discrete Math. 3 pp 259– (1978)
[154] Thomassen, Proc. London Math. Soc (3) 42 pp 231– (1981)
[155] Connectivity in tournaments. Graph Theory and Combinatorics, Academic Press, Orlando, FL (1984) 305–313.
[156] Thompson, Discrete Appl. Math. 10 pp 179– (1985)
[157] Tomescu, Rev. Roumaine Math. Press Appl. 29 pp 499– (1984)
[158] Turner, J. Combin. Theory B 3 pp 136– (1967)
[159] Tutte, J. London Math. Soc. 21 pp 98– (1946)
[160] ed., Recent Progress in Combinatorics. Academic Press, New York (1969).
[161] Veldman, Discrete Math. 43 pp 281– (1983)
[162] Veldman, Discrete Math. 44 pp 309– (1983)
[163] Witte, Discrete Math. 51 pp 293– (1984)
[164] Woodall, J. Combinat. Theory B 22 pp 274– (1977)
[165] Zaks, J. Combinat. Theory B 21 pp 116– (1976)
[166] Zaks, J. Combinat. Theory B 32 pp 95– (1982)
[167] Zhan, Ars Combinat. 22 pp 89– (1986)
[168] Zhang, J. Graph Theory 12 pp 209– (1988)
[169] , and , An improvement of Jackson’s result on Hamilton cycles in 2-connected regular graphs. Cycles in Graphs (Burnaby, B. C., 1982), North Holland Mathematics Studies, Vol. 115. North Holland, Amsterdam (1985) 237–247.
[170] Zhu, J. Combinat. Theory Ser. B. 35 pp 247– (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.