×

Generalizations of Dirac’s theorem in Hamiltonian graph theory – a survey. (English) Zbl 1277.05100

Summary: G. Dirac showed in [Proc. Lond. Math. Soc., III. Ser. 2, 69–81 (1952; Zbl 0047.17001)] that every graph of order \(n\) is Hamiltonian if any vertex is of degree at least \(\frac{n}{2}\). This result has played an important role in extremal Hamiltonian graph theory. This paper is a survey on some recent results on generalization of Dirac’s theorem.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles

Citations:

Zbl 0047.17001
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ainouche, A.; Christofides, N., Conditions for the existence of Hamiltonian circuits in graphs based on vertex degrees, Journal of the London Mathematical Society (2), 32, 385-391 (1985) · Zbl 0598.05045
[2] Amar, D.; Flandrin, E.; Fournier, I.; Germa, A., Pancyclism in Hamiltonian graphs, Discrete Mathematics, 89, 111-131 (1991) · Zbl 0727.05039
[4] Ash, P.; Jackson, B., Dominating cycles in 2-connected bipartite graphs, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press), 81-87
[6] Bauer, D.; Broersma, H. J.; Li, R.; Veldman, H. J., A genaralization of a result of Haggkvist and Nicoghossian, Journal of Combinatorial Theory, Series B, 47, 237-243 (1989) · Zbl 0634.05053
[7] Bauer, D.; Morgana, A.; Schmeichel, E. F.; Veldman, H. J., Long cycles in graphs with large degree sums, Discrete Mathematics, 79, 59-70 (1989-1990) · Zbl 0713.05041
[9] Bauer, D.; Schmeichel, E. F.; Veldman, H. J., A generalization of a theorem of Bigalke and Jung, Ars Combinatoria, 26, 53-58 (1988) · Zbl 0668.05040
[10] Benhocine, A.; Wojda, A. P., The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs, Journal of Combinatorial Theory, Series B, 42, 167-180 (1987) · Zbl 0613.05038
[11] Bermond, J. C., On Hamiltonian walks, (Nash-Williams, C. St. J.A.; Sheehan, J., Proc. Fifth Brit. Comb. Conf. (1976), Utilitas Math.), 41-51 · Zbl 0329.05113
[12] Bermond, J. C., Hamiltonian graphs, (Beineke; Wilson, Selected Topics in Graph Theory (1978), Academic Press: Academic Press London) · Zbl 0429.05052
[13] Bigalke, A.; Jung, H. A., Über Hamiltonsche Kreise und unabhängige Ecken in Graphen, Monatshefte für Chemie, 88, 195-210 (1979) · Zbl 0396.05033
[14] Bollobás, B., Extremal graph theory, (Handbook of Combinatorics, Vol. II (1995), Elsevier: Elsevier Amsterdam, Lausanne, New York, Oxford, Shannon, Tokyo), 1231-1292 · Zbl 0844.05054
[15] Bollobás, B.; Brightwell, G., Cycles through specified vertices, Combinatorica, 13, 147-155 (1993) · Zbl 0780.05033
[16] Bollobás, B.; Hobbs, A. M., Hamiltonian cycles in regular graphs, (Advances in Graph Theory (1978), North Holland: North Holland Amsterdam) · Zbl 0376.05036
[17] Bollobás, B.; Thomason, A., Weakly pancyclic graphs, Journal of Combinatorial Theory, Series B, 77, 121-137 (1999) · Zbl 1023.05083
[18] Bondy, J. A., Large cycles in graphs, Discrete Mathematics, 1, 121-131 (1971) · Zbl 0224.05120
[19] Bondy, J. A., Pancyclic graphs, Journal of Combinatorial Theory, 11, 80-84 (1971) · Zbl 0183.52301
[22] Bondy, J. A., Basic graph theory: paths and circuits, (Handbook of Combinatorics Volume I (1995), Elsevier: Elsevier Amsterdam, Lausanne, New York, Oxford, Shannon, Tokyo), 3-110 · Zbl 0849.05044
[24] Bondy, J. A.; Chvatal, V., A method of graph theory, Discrete Mathematics, 15, 111-136 (1976) · Zbl 0331.05138
[25] Bondy, J. A.; Kouider, M., Hamilton cycles in regular 2-connected graphs, Journal of Combinatorial Theory, Series B, 177-186 (1988)
[26] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Elsevier: Elsevier New York · Zbl 1226.05083
[27] Brandt, S., A sufficient condition for all short cycles, Discrete Applied Mathematics, 79, 63-66 (1997) · Zbl 0882.05081
[28] Brandt, S.; Faudree, R. J.; Goddard, W., Weakly pancyclic graphs, Journal of Graph Theory, 27, 141-176 (1998) · Zbl 0927.05045
[29] Broersma, H. J.; Li, H.; Li, J. P.; Tian, F.; Veldman, H. J., Cycles through subsets with large degree sums, Discrete Mathematics, 171, 43-54 (1997) · Zbl 0883.05089
[30] Broersma, H. J.; Van Den Heuvel, J.; Jackson, B.; Veldman, H. J., Hamiltonicity of regular 2-connected graphs, Journal of Graph Theory, 22, 105-124 (1996) · Zbl 0864.05058
[31] Broersma, H. J.; Van Den Heuvel, J.; Veldman, H. J., A generalization of Ore’s theorem involving neighborhood unions, Discrete Mathematics, 122, 37-49 (1993) · Zbl 0789.05058
[33] Chen, G., Longest cycles in 2-connected graphs, Journal of Central China Normal University. Natural Sciences, 3, 39-42 (1986)
[34] Chen, G.; Liu, Y., Hamiltonian graphs with large neighborhood unions, Ars Combinatoria, 46, 227-238 (1997) · Zbl 0933.05092
[35] Chen, G.; Schelp, R. H., Hamiltonian graphs involving distances, Journal of Graph Theory, 16, 121-129 (1992) · Zbl 0766.05053
[36] Chen, G.; Schelp, R. H., Hamiltonian graphs with neighborhood intersection, Journal of Graph Theory, 18, 497-513 (1994) · Zbl 0803.05039
[37] Chen, B.; Zhang, S., An implicit degree condition for long cycles in 2-connected graphs, Applied Mathematics Letters, 19, 1148-1151 (2006) · Zbl 1172.05329
[39] Chvátal, V., On Hamilton’s ideals, Journal of Combinatorial Theory, Series B, 12, 163-168 (1972) · Zbl 0213.50803
[40] Chvátal, V.; Erdös, P., A note on Hamiltonian circuits, Discrete Mathematics, 2, 111-113 (1972) · Zbl 0233.05123
[41] Dirac, G., Some theorems on abstract graphs, Proceedings of the London Mathematical Society, 2, 69-81 (1952) · Zbl 0047.17001
[42] Egawa, Y., Edge-disjoint Hamiltonian cycles in graphs of Ore type, SUT Journal of Mathematics, 29, 15-50 (1993) · Zbl 0805.05050
[43] Enomoto, H.; Heuvel, J. V.D.; Kaneko, A.; Saito, A., Relative length of long paths and cycles in graphs with large degree sums, Journal of Graph Theory, 20, 213-225 (1995) · Zbl 0841.05057
[44] Erdös, P.; Hobbs, A. M., Hamiltonian cycles in regular graphs, (Advances in Graph Theory (1978), North Holland: North Holland Amsterdam)
[45] Fan, G., New sufficient conditions for cycles in graphs, Journal of Combinatorial Theory, Series B, 37, 221-227 (1984) · Zbl 0551.05048
[46] Fan, G., Longest cycles in regular graphs, Journal of Combinatorial Theory, Series B, 39, 325-345 (1985) · Zbl 0584.05046
[47] Faudree, R.; Favaron, O.; Flandrin, E.; Li, H., Pancyclism and small cycles in graphs, Discussiones Mathematicae. Graph Theory, 16, 27-40 (1996) · Zbl 0879.05042
[48] Faudree, R.; Flandrin, E.; Ryjácek, Z., Claw-free graphs—a survey, Discrete Mathematics, 164, 87-147 (1997) · Zbl 0879.05043
[49] Faudree, R. J.; Gould, R. J.; Jacobson, M. S.; Lesniak, L. M., Neighborhood unions and highly Hamiltonian graphs, Ars Combinatoria, 31, l39-148 (1991) · Zbl 0739.05056
[50] Faudree, R. J.; Gould, R. J.; Jacobson, M. S.; Schelp, R. H., Neighborhood unions and Hamiltonian properties in graphs, Journal of Combinatorial Theory, Series B, 47, 121-157 (1991)
[51] Faudree, R. J.; Rousseau, C. C.; Schelp, R. H., Edge-disjoint Hamiltonian cycles, (Graph Theory and its Applications to Algorithm and Computer Science (1985)), 231-249 · Zbl 0579.05039
[52] Favaron, O.; Flandrin, E.; Li, H.; Liu, Y. P.; Tian, F.; Wu, Z. S., Sequences, claws and cyclability of graphs, Journal of Graph Theory, 21, 357-369 (1996) · Zbl 0849.05045
[53] Favaron, O.; Flandrin, E.; Li, H.; Tian, F., An Ore-type condition for pancyclability, Discrete Mathematics, 206, 139-144 (1999) · Zbl 0929.05045
[54] Flandrin, E.; Jung, H. A.; Li, H., Hamiltonism, degree sum and neighbourhood intersections, Discrete Mathematics, 90, 41-52 (1991) · Zbl 0746.05038
[55] Flandrin, E.; Li, H.; Marczyk, A.; Wozniam, M., A note on a generalisation of Ore’s condition, Graphs and Combinatorics, 21, 213-216 (2005) · Zbl 1067.05039
[56] Fournier, I.; Fraisse, P., On a conjecture of Bondy, Journal of Combinatorial Theory, Series B, 39, 17-26 (1985) · Zbl 0576.05035
[57] Fraisse, P., A new sufficient condition for Hamiltonian graphs, Journal of Graph Theory, 10, 405-409 (1986) · Zbl 0606.05043
[58] Gould, R. J., Updating the Hamiltonian problem—a survey, Journal of Graph Theory, 15, 121-157 (1991) · Zbl 0746.05039
[59] Gould, R. J., Advances on the Hamiltonian problem—a survey, Graphs and Combinatorics, 19, 7-52 (2003) · Zbl 1024.05057
[61] Häggkvist, R.; Faudree, R. J.; Schelp, R. H., Pancyclic graphs—connected Ramsey number, Ars Combinatoria, 11, 37-49 (1981) · Zbl 0485.05038
[62] Häggkvist, R.; Jackson, B., A note on maximal cycles in 2-connected graphs, Annals of Discrete Mathematics, 27, 205-208 (1985) · Zbl 0573.05038
[64] Häggkvist, R.; Nicoghossian, G. G., A remark on Hamiltonian cycles, Journal of Combinatorial Theory, Series B, 30, 118-120 (1981) · Zbl 0462.05046
[65] Harkat-Benhamdine, A.; Li, H.; Tian, F., Cyclability of 3-connected graphs, Journal of Graph Theory, 34, 191-203 (2000) · Zbl 0955.05060
[67] Hu, Z.; Li, H., Removable matchings and Hamiltonian cycles, Discrete Mathematics, 309, 1020-1024 (2009) · Zbl 1179.05087
[68] Jackson, B., Edge disjoint Hamilton cycles in regular graphs of large degree, Journal of the London Mathematical Society, 19, 13-16 (1979) · Zbl 0394.05032
[69] Jackson, B., Hamilton cycles in regular 2-connected graphs, Journal of Combinatorial Theory. Series B, 29, 27-46 (1980) · Zbl 0377.05027
[70] Jackson, B., Longest cycles in 3-connected cubic graphs, Journal of Combinatorial Theory. Series B, 41, 17-26 (1986) · Zbl 0591.05040
[71] Jackson, B., Neighborhood unions and Hamilton cycles, Journal of Graph Theory, 15, 443-451 (1991) · Zbl 0739.05058
[72] Jackson, B.; Li, H., Hamilton cycles in 2-connected regular bipartite graphs, Journal of Combinatorial Theory. Series B, 62, 236-258 (1994) · Zbl 0807.05051
[73] Jackson, B.; Li, H.; Zhu, Y., Dominating cycles in regular 3-connected graphs, Discrete Mathematics, 102, 163-176 (1991) · Zbl 0756.05075
[74] Jung, H. A., On maximal circuits in finite graphs, Annals of Discrete Mathematics, 3, 129-144 (1978) · Zbl 0399.05039
[77] Li, H., Hamilton cycles in regular graphs, Science Bulletin of China, 474-475 (1988)
[78] Li, H., Edge disjoint cycles in graphs, Journal of Graph Theory, 13, 313-322 (1989) · Zbl 0676.05053
[79] Li, H., Circumferences in 1-touch graphs, Discrete Mathematics, 146, 325-328 (1995)
[80] Li, G., Edge disjoint Hamilton cycles in graphs, Journal of Graph Theory, 35, 8-20 (2000) · Zbl 0955.05065
[81] Li, H., On cycles in 3-connected graphs, Graphs and Combinatorics, 16, 319-335 (2000) · Zbl 0963.05078
[82] Li, H., On a conjecture of Woodall, Journal of Combinatorial Theory. Series B, 86, 172-185 (2002) · Zbl 1023.05086
[83] Li, P., Implicit weighted degree condition for heavy paths in weighted graphs, Journal of Shandong University. Natural Science, 18, 11-13 (2003)
[89] Li, H.; Ning, W.; Cai, J., An implicit degree condition for cyclability in graphs, Lecture Notes in Computer Science, 6681, 82-89 (2011) · Zbl 1329.05164
[90] Li, H.; Ning, W.; Cai, J., An implicit degree condition for Hamiltonian graphs, Discrete Mathematics, 312, 2190-2196 (2012) · Zbl 1244.05137
[92] Li, H.; Tian, F.; Xu, Z., Hamiltonicity of 4-connected graphs, Acta Mathematica Sinica, 26, 4, 699-710 (2010) · Zbl 1190.05083
[93] Li, H.; Zhou, S.; Wang, G., The \(k\)-dominating cycles in graphs, European Journal of Combinatorics, 31, 608-616 (2010) · Zbl 1208.05100
[94] Li, H.; Zhu, Y., Edge-disjoint Hamiltonian cycles in graphs, (Graph Theory and its Applications: East and West. Graph Theory and its Applications: East and West, Annales of the New York Academy of Sciences, vol. 576 (1990)), 311-322 · Zbl 0794.05071
[95] Li, H.; Zhu, Y., Hamiltonian cycles in regular 3-connected graphs, Discrete Mathematics, 110, 229-249 (1992) · Zbl 0774.05063
[97] Linial, N., A lower bound on circumferences of a graph, Discrete Mathematics, 15, 297-300 (1976) · Zbl 0344.05139
[98] Liu, Y.; Tian, F.; Wu, Z., A \(k\)-Hamilton-nice sequence, Systems Science and Mathematical Sciences, 8, 144-151 (1995) · Zbl 0841.05063
[99] Lu, M.; Liu, H. Q.; Tian, F., Two sufficient conditions for dominating cycles, Journal of Graph Theory, 49, 135-150 (2005) · Zbl 1064.05114
[100] Nara, C., On sufficient conditions for a graph to be Hamiltonian, Natural Science Report of the Ochanomizu University, 31, 2, 75-80 (1980) · Zbl 0468.05053
[101] Nash-Williams, C. St. J.A., Edge disjoint Hamiltonian circuits in graphs with vertices of large valency, (Studies in Pure Math. (1971), Academic Press: Academic Press London), 157-183 · Zbl 0223.05123
[102] Nash-Williams, C. St. J.A., Hamilton arcs and circuit, (Capobianco, M.; Frechen, J. B.; Krolik, M., Recent Trends in Graph Theory. Recent Trends in Graph Theory, Lecture Notes in Mathematics, vol. 186 (1971), Springer: Springer Berlin), 197-210
[103] Ore, O., Note on hamilton circuits, American Mathematical Monthly, 67, 55 (1960) · Zbl 0089.39505
[104] Ota, K., Cycles through prescribed vertices with large degree sum, Discrete Mathematics, 145, 201-210 (1995) · Zbl 0838.05071
[105] Ozeki, K.; Tsugaki, M.; Yamashita, T., On relative length of longest paths and cycles, Journal of Graph Theory, 62, 3, 79-291 (2009) · Zbl 1229.05183
[106] Ozeki, K.; Yamashita, T., A degree sum condition concerning the connectivity and the independence number of a graph, Graphs and Combinatorics, 24, 469-483 (2008) · Zbl 1176.05044
[107] Schelten, U.; Schermeyer, I., Small cycles in Hamiltonian graphs, Discrete Mathematics, 79, 201-211 (1997) · Zbl 0882.05082
[108] Schmeichel, E. F.; Hakimi, S. L., Pancyclic graphs and a conjecture of Bondy and Chvátal, Journal of Combinatorial Theory. Series B, 17, 22-34 (1974) · Zbl 0279.05120
[109] Schmeichel, E. F.; Hakimi, S. L., A cycle structure theorem for Hamiltonian graphs, Journal of Combinatorial Theory. Series B, 45, 99-107 (1988) · Zbl 0607.05050
[110] Schmeichel, E.; Hayes, D., Some extensions of Ore’s Theorem, (Graph Theory with Applications to Algorithms and Computer Science (1985)), 687-695
[111] Shi, R. H., The Ore-type conditions on pancyclism of Hamiltonian graphs, Journal of Systems Science and Mathematical Sciences, 11, 79-90 (1991) · Zbl 0729.05031
[112] Shi, R., 2-neighborhoods and Hamiltonian conditions, Journal of Graph Theory, 16, 267-271 (1992) · Zbl 0761.05066
[113] Stacho, L., Locally pancyclic graphs, Journal of Combinatorial Theory. Series B, 76, 22-40 (1999) · Zbl 0929.05047
[114] Tsugaki, M.; Yamashita, T., Dominating cycles in graphs with high connectivity, Ars Combinatoria, 91, 113-121 (2009) · Zbl 1224.05384
[115] Wei, B., Longest cycles in 3-connected graphs, Discrete Mathematics, 170, 195-201 (1997) · Zbl 0905.05042
[116] Woodall, D. R., The binding number of a graph and its Anderson number, Journal of Combinatorial Theory. Series B, 15, 225-255 (1973) · Zbl 0253.05139
[117] Woodall, D. R., Maximal circuits of graphs II, Studia Scientiarum Mathematicarum Hungarica, 10, 103-109 (1975) · Zbl 0361.05042
[118] Yamashita, T., A degree sum condition for longest cycles in 3-connected graphs, Journal of Graph Theory, 54, 4, 277-283 (2007) · Zbl 1124.05052
[119] Yamashita, T., On degree sum conditions for long cycles and cycles through specified vertics, Discrete Mathematics, 308, 6584-6587 (2008) · Zbl 1169.05023
[120] Yamashita, T., A degree sum condition with connectivity for relative length of longest path and cycles, Discrete Mathematics, 309, 23-24, 6503-6507 (2009) · Zbl 1226.05091
[121] Zhang, S.; Li, X.; Broersma, H., A \(\sigma_3\) type condition for heavy cycles in weighted graphs, Discussiones Mathematicae. Graph Theory, 21, 159-166 (2001) · Zbl 1002.05047
[122] Zhang, C. Q.; Zhu, Y., Long path connectivity of regular graphs, Discrete Mathematics, 96, 151-160 (1991) · Zbl 0753.05050
[123] Zhang, C. Q.; Zhu, Y., Factorizations of regular graphs, Journal of Combinatorial Theory. Series B, 56, 74-89 (1992) · Zbl 0711.05036
[124] Zhou, S., Disjoint Hamiltonian cycles in Fan 2k-type graphs, Journal of Graph Theory, 3, 313-322 (1989)
[126] Zhu, Y.; Gao, J., Implicit degrees and Chvátal condition for hamiltonicity, Journal of Systems Science and Complexity, 2, 353-363 (1989) · Zbl 0719.05046
[127] Zhu, Y.; Li, H., The progress of Hamilton problems in graph theory, Journal of Qufu Teachers College, 2, 12-22 (1985)
[128] Zhu, Y.; Li, H.; Deng, X., Implicit-degrees and circumferences, Graphs and Combinatorics, 5, 283-290 (1989) · Zbl 0701.05030
[129] Zhu, Y.; Liu, Z.; Yu, Z., An improvement of Jackson’s result on Hamilton cycles in 2-connected regular graphs, (Alspach, B. R.; Godsil, C. D., Cycles in Graphs. Cycles in Graphs, Ann. Disc. Math., vol. 27 (1985)), 237-247
[130] Zhu, Y.; Liu, Z.; Yu, Z., 2-connected \(k\)-regular graphs on at most \(3 k + 3\) vertices to be Hamiltonian, Journal of Systems Science and Mathematical Sciences, 6, 36-49 (1986), and 136-145 · Zbl 0599.05043
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.