Toughness in graphs – a survey. (English) Zbl 1088.05045
Summary: In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!
MSC:
| 05C40 | Connectivity |
| 05C45 | Eulerian and Hamiltonian graphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
Keywords:
Hamilton cycle; Hamiltonian graph; Traceable graph; Circumference; Factor; Chordal graph; Triangle-free graph; Planar graph; Computational complexityReferences:
| [1] | Ainouche, A.; Christofides, N., Conditions for the existence of harniltonian circuits in graphs based on vertex degrees, J London Math Soc, 32, 385-391 (1985) · Zbl 0598.05045 |
| [2] | Alon, N., Tough ramsey graphs without short cycles, Journal of Algebraic Combinatorics, 4, 189-195 (1995) · Zbl 0826.05039 |
| [3] | Balakrishnan, R.; Paulraja, P., Chordal graphs and some of their derived graphs, Congr Numer, 53, 71-74 (1986) · Zbl 0641.05037 |
| [4] | Barefoot, C. A.; Entringer, R.; Swart, H., Vulnerability in graphs - a comparative survey, J. Combin. Math. Combin. Comput, 1, 13-22 (1987) · Zbl 0646.05042 |
| [5] | Bauer, D.; Broersma, H. J.; Heuvel, J.; Veldman, H. J., On hamiltonian properties of 2-tough graphs, J. Graph Theory, 18, 539-543 (1994) · Zbl 0815.05042 |
| [6] | Bauer, D.; Broersma, H. J.; Heuvel, J.; Veldman, H. J., Long cycles in graphs with prescribed toughness and minimum degree, Discrete Math., 141, 1-10 (1995) · Zbl 0831.05039 |
| [7] | Bauer, D., Broersma, H.J., Kahl, N., Morgana, A., Schmeichel, E., Surowiec, T.: Tutte sets in graphs II: the complexity of finding maximum Tutte sets. Preprint (2005) · Zbl 1119.05086 |
| [8] | Bauer, D.; Broersma, H. J.; Li, R.; Veldman, H. J.; Combin, J., A generalization of a result of Häggkvist and Nicoghossian, Theory - Ser B, 47, 237-243 (1989) · Zbl 0634.05053 |
| [9] | Bauer, D.; Broersma, H. J.; Morgana, A.; Schmeichel, E., Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion, Discrete Appl Math, 120, 13-23 (2002) · Zbl 1052.68097 |
| [10] | Bauer, D., Broersma, H.J., Schmeichel, E.: More progress on tough graphs - The Y2K report. In: Alavi, Y., Jones, D., Lick, D.R., Liu, J. (eds.), Electronic Notes in Discrete Math. - Proceedings of the Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications 11, 1-18 (2002) · Zbl 1075.05559 |
| [11] | Bauer, D., Broersma, H.J., Veldman, H.J.: Around three lemmas in hamiltonian graph theory, Topics in Combinatorics and Graph Theory. Physica-Verlag, Heidelberg, pp 101-110 (1990) · Zbl 0736.05054 |
| [12] | Bauer, D.; Broersma, H. J.; Veldman, H. J., On generalizing a theorem of Jung, Ars Combinatoria, 40, 207-218 (1995) · Zbl 0843.05071 |
| [13] | Bauer, D.; Broersma, H. J.; Veldman, H. J., Not every 2-tough graph is hamiltonian, Discrete Appl. Math, 99, 317-321 (2000) · Zbl 0934.05083 |
| [14] | Bauer, D., Chen, G., Lasser, L.: A degree condition for hamilton cycles in t-tough graphs with t>1. Advances in Graph Theory. Vishwa Int Publ 20-33 (1991) |
| [15] | Bauer, D.; Fan, G.; Veldman, H. J., Hamiltonian properties of graphs with large neighborood unions, Discrete Math, 96, 33-49 (1991) · Zbl 0741.05039 |
| [16] | Bauer, D.; Hakimi, S. L.; Schmeichel, E., Recognizing tough graphs is NP-hard, Discrete Appl. Math, 28, 191-195 (1990) · Zbl 0706.68052 |
| [17] | Bauer, D.; Heuvel, J.; Morgana, A.; Schmeichel, E., The complexity of recognizing tough cubic graphs, Discrete Appl. Math, 79, 35-44 (1997) · Zbl 0888.68092 |
| [18] | Bauer, D.; Heuvel, J.; Morgana, A.; Schmeichel, E., The complexity of toughness in regular graphs, Congr. Numer, 130, 47-61 (1998) · Zbl 0986.68531 |
| [19] | Bauer, D.; Heuvel, J.; Schmeichel, E., Toughness and triangle-free graphs, J Combin. Theory - Ser. B, 65, 208-221 (1995) · Zbl 0835.05034 |
| [20] | Bauer, D.; Heuvel, J.; Schmeichel, E., 2-Factors in triangle-free graphs, J Graph Theory, 21, 405-412 (1996) · Zbl 0865.05060 |
| [21] | Bauer, D.; Jung, H. A.; Schmeichel, E., On 2-connected graphs with small circumference, J Combin. Inform. Systems Sci, 15, 16-24 (1990) · Zbl 0742.05051 |
| [22] | Bauer, D.; Katona, G. Y.; Kratsch, D.; Veldman, H. J., Chordality and 2-factors in tough graphs, Discrete Appl. Math, 99, 323-329 (2000) · Zbl 0937.68094 |
| [23] | Bauer, D.; Morgana, A.; Schmeichel, E., A simple proof of a theorem of Jung, Discrete Math, 79, 147-152 (1990) · Zbl 0707.05045 |
| [24] | Bauer, D.; Morgana, A.; Schmeichel, E., On the complexity of recognizing tough graphs, Discrete Math, 124, 13-17 (1994) · Zbl 0802.68065 |
| [25] | Bauer, D.; Morgana, A.; Schmeichel, E.; Veldman, H. J., Long cycles in graphs with large degree sums, Discrete Math, 79, 59-70 (1989) · Zbl 0713.05041 |
| [26] | Bauer, D.; Niessen, T.; Schmeichel, E., Toughness, minimum degree, and spanning cubic subgraphs, J Graph Theory, 45, 119-141 (2004) · Zbl 1033.05065 |
| [27] | Bauer, D., Schmeichel, E.: Long cycles in tough graphs, Stevens Research Reports in Mathematics 8612. Stevens Institute of Technology, Hoboken, New Jersey 07030 (1986) · Zbl 0840.05049 |
| [28] | Bauer, D., Schmeichel, E.: On a theorem of Häggkvist and Nicoghossian. In: Alavi, Y., Chung, F.R.K., Graham, R.L., Hsu, D.S. (eds.), Graph Theory, Combinatorics, Algorithms, and Applications - Proceedings 2^nd China-USA Graph Theory Conference. SIAM pp 20-25 (1991) · Zbl 0741.05040 |
| [29] | Bauer, D.; Schmeichel, E., Toughness, minimum degree and the existence of 2-factors, J Graph Theory, 18, 241-256 (1994) · Zbl 0795.05081 |
| [30] | Bauer, D., Schmeichel, E., H. J. Veldman, Some recent results on long cycles in tough graphs, In Alavi, Y., Chartrand, G., Oellermann, O. R., Schwenk, A. J. eds.. Graph Theory, Combinatorics, and Applications - Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs (John Wiley & Sons, Inc., New York, 1991) 113-121. · Zbl 0840.05049 |
| [31] | Bauer, D.; Schmeichel, E.; Veldman, H. J., A note on dominating cycles in 2-connected graphs, Discrete Math, 155, 13-18 (1996) · Zbl 0864.05052 |
| [32] | Bauer, D., Schmeichel, E., Veldman, H.J.: Cycles in tough graphs – updating the last four years. In: Alavi, Y., Schwenk, A. J. (eds.), Graph Theory, Combinatorics, and Applications - Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs. John Wiley & Sons, Inc., New York, pp 19-34 (1995) · Zbl 0842.05057 |
| [33] | Bauer, D., Schmeichel, E., Veldman, H.J., Progress on tough graphs - another four years. In: Alavi, Y., Lick, D.R., Schwenk, A.J. (eds.), Proceedings of the Eighth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications. John Wiley & Sons, Inc., New York, pp 69-88, 1999 |
| [34] | Beineke, L. W.; Goddard, W.; Vandell, R., More measures of vulnerability: Splinter sets and directed toughness, Congr Numer, 155, 81-88 (2002) · Zbl 1026.05070 |
| [35] | Berge, C., Two theorems in graph theory, Proc. Nat. Acad. Sci. USA, 43, 842-844 (1957) · Zbl 0086.16202 |
| [36] | Bermond, J. C., On Hamiltonian walks, Congr Numer, 15, 41-51 (1976) · Zbl 0329.05113 |
| [37] | Bermond, J.C.: Hamiltonian graphs. In: Beineke, L., Wilson, R.J. (eds.), Selected Topics in Graph Theory. Academic Press, London and New York, pp 127-167, 1978 · Zbl 0429.05052 |
| [38] | Bertossi, A. A., The edge hamiltonian path problem is NP-complete, Inform Process Lett, 13, 157-159 (1981) · Zbl 0495.68058 |
| [39] | Bigalke, A.; Jung, H. A., Über Hamiltonische Kreise und unabhängige Ecken in Graphen, Monatsh Math, 88, 195-210 (1979) · Zbl 0396.05033 |
| [40] | Böhme, T.; Broersma, H. J.; Veldman, H. J., Toughness and longest cycles in 2-connected planar graphs, J. Graph Theory, 23, 257-263 (1996) · Zbl 0866.05034 |
| [41] | Böhme, T.; Harant, J.; Tkáč, M., More than 1-tough chordal planar graphs are hamiltonian, J. Graph Theory, 32, 405-410 (1999) · Zbl 0939.05056 |
| [42] | Bondy, J. A., Large cycles in graphs, Discrete Math, 1, 121-131 (1971) · Zbl 0224.05120 |
| [43] | Bondy, J.A.: Pancyclic graphs I. J. Combin. Theory - Ser. B 11, 80-84 (1971) · Zbl 0183.52301 |
| [44] | Bondy, J.A.: Longest paths and cycles in graphs of high degree, Research Report CORR 80- 16. University of Waterloo, Waterloo, Ontario (1980) |
| [45] | Bondy, J.A., Broersma, H.J., Hoede, C., Veldman, H. J. (eds.), Progress Report EIDMA Workshop on Hamiltonicity of 2-Tough Graphs. Technical report, University of Twente, The Netherlands (1996) |
| [46] | Bondy, J. A.; Simonovits, M., Longest cycles in 3-connected 3-regular graphs, Can. J Math, 32, 987-992 (1980) · Zbl 0454.05043 |
| [47] | Brandt, S., Cycles and paths in triangle-free graphs, Algorithms Combin, 14, 32-42 (1997) · Zbl 0867.05036 |
| [48] | Brandt, S.: Sufficient conditions for graphs to contain all subgraphs of a given type. PhD thesis, Freie Universität Berlin (1995) |
| [49] | Brandt, S.: Triangle-free graphs whose independence number equals the degree. Preprint, 1996 · Zbl 1216.05097 |
| [50] | Brandt, S.; Faudree, R.; Goddard, W., Weakly pancyclic graphs, J. Graph Theory, 27, 141-176 (1998) · Zbl 0927.05045 |
| [51] | Brandt, S.; Veldman, H. J., Degree sums for edges and cycle lengths in graphs, J. Graph Theory, 25, 253-256 (1997) · Zbl 0876.05056 |
| [52] | Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 1999 · Zbl 0919.05001 |
| [53] | Broersma, H. J.; Engbers, E.; Trommel, H., Various results on the toughness of graphs, NETWORKS, 33, 233-238 (1999) · Zbl 0923.05035 |
| [54] | Broersma, H. J.; Heuvel, J.; Jung, H. A.; Veldman, H. J., Long paths and cycles in tough graphs, Graphs and Combin, 9, 3-17 (1993) · Zbl 0778.05047 |
| [55] | Broersma, H.J., van den Heuvel, J., Veldman, H.J. (eds.), Updated Contributions to the Twente Workshop on Hamiltonian Graph Theory. Technical report, University of Twente, The Netherlands, (1992) |
| [56] | Broersma, H. J.; Heuvel, J.; Veldman, H. J., Long cycles, degree sums and neighborhood unions, Discrete Math, 121, 25-35 (1993) · Zbl 0791.05063 |
| [57] | Broersma, H.J., Xiong, L., Yoshimoto, K.: Toughness and hamiltonicity in k-trees, To appear in Discrete Math. · Zbl 1117.05069 |
| [58] | Brouwer, A. E., Toughness and spectrum of a graph, Linear Algebra Appl, 226, 267-271 (1995) · Zbl 0833.05048 |
| [59] | Cai, M.; Favaron, O.; Li, H., (2,k)-factor-critical graphs and toughness, Graphs and Combin, 15, 137-142 (1999) · Zbl 0930.05076 |
| [60] | Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall, London, 1996 · Zbl 0890.05001 |
| [61] | Chen, C., Toughness of graphs and k-factors with given properties, Ars Combinatoria, 34, 55-64 (1992) · Zbl 0770.05078 |
| [62] | Chen, C., Toughness of graphs and [2,b]-factors, Graphs and Combin, 10, 97-100 (1994) · Zbl 0805.05061 |
| [63] | Chen, G.; Jacobson, M. S.; Kézdy, A. E.; Lehel, J., Tough enough chordal graphs are hamiltonian, NETWORKS, 31, 29-38 (1998) · Zbl 0894.90150 |
| [64] | Chen, G.; Yu, X., Long cycles in 3-connected graphs, J Combin Theory - Ser B, 86, 80-99 (2002) · Zbl 1025.05036 |
| [65] | Chvátal, V.: On Hamilton’s ideals. J Combin. Theory - Ser. B 12, 163-168 (1972) · Zbl 0213.50803 |
| [66] | Chvátal, V.: Private communication |
| [67] | Chvátal, V., Tough graphs and hamiltonian circuits, Discrete Math, 5, 215-228 (1973) · Zbl 0256.05122 |
| [68] | Chvátal, V.: Hamiltonian cycles. In: Lawler, E. L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, B. (eds.), The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Chichester, pp 403-429, 1985 · Zbl 0562.00014 |
| [69] | Chvátal, V.; Erdös, P., A note on hamiltonian circuits, Discrete Math, 2, 111-113 (1972) · Zbl 0233.05123 |
| [70] | Colbourn, C. J.; Stewart, L. K., Dominating cycles in series-parallel graphs, Ars Combinatoria, 19a, 107-112 (1985) · Zbl 0568.05035 |
| [71] | Cunningham, W. H., On submodular function minimization, Combinatorica, 5, 185-192 (1985) · Zbl 0647.05018 |
| [72] | Dankelmann, P.; Niessen, T.; Schiermeyer, I., On path-tough graphs, SIAM J Disc. Math, 7, 571-584 (1994) · Zbl 0824.05041 |
| [73] | Deogun, J. S.; Kratsch, D.; Steiner, G., 1-Tough cocomparability graphs are hamiltonian, Discrete Math, 170, 99-106 (1997) · Zbl 0876.05066 |
| [74] | Descartes, B., A three colour problem, Eureka, 9, 21 (1947) |
| [75] | Dillencourt, M. B., An upper bound on the shortness exponent of 1-tough maximal planar graphs, Discrete Math, 90, 93-97 (1991) · Zbl 0729.05029 |
| [76] | Dillencourt, M. B., On the toughness index of planar graphs, J Graph Theory, 18, 103-107 (1994) · Zbl 0788.05031 |
| [77] | Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc, 2, 69-81 (1952) · Zbl 0047.17001 |
| [78] | Doty, L., A large class of maximally tough graphs, OR Spektrum, 13, 147-151 (1991) · Zbl 0758.05059 |
| [79] | Ellingham, N. N.; Nam, Y.; Voss, H. J., Connected (g,f)-factors, J. Graph Theory, 39, 62-75 (2002) · Zbl 0995.05117 |
| [80] | Ellingham, M. N.; Zha, X., Toughness, trees, and k-walks, J. Graph Theory, 33, 125-137 (2000) · Zbl 0951.05068 |
| [81] | Enomoto, H., Toughness and the existence of k-factors II, Graphs and Combin, 2, 37-42 (1986) · Zbl 0652.05045 |
| [82] | Enomoto, H., Toughness and the existence of k-factors III, Discrete Math, 189, 277-282 (1998) · Zbl 0955.05085 |
| [83] | Enomoto, H.; Hagita, M., Toughness and the existence of k-factors IV, Discrete Math, 216, 111-120 (2000) · Zbl 0952.05057 |
| [84] | Enomoto, H.; Jackson, B.; Katerinis, P.; Saito, A., Toughness and the existence of k-factors, J Graph Theory, 9, 87-95 (1985) · Zbl 0598.05054 |
| [85] | Erdös, P., Graph theory and probability, Can. J. Math., 11, 34-38 (1959) · Zbl 0084.39602 |
| [86] | Fan, G., New sufficient conditions for cycles in graphs, J. Combin. Theory - Ser B, 37, 221-227 (1984) · Zbl 0551.05048 |
| [87] | Faßbender, B., A sufficient condition on degree sums of independent triples for hamiltonian cycles in 1-tough graphs, Ars Combinatoria, 33, 300-304 (1992) · Zbl 0764.05050 |
| [88] | Faudree, R.; Gould, R.; Jacobson, M.; Lesniak, L.; Saito, A., Toughness, degrees and 2-factors, Discrete Math, 286, 245-249 (2004) · Zbl 1060.05056 |
| [89] | Favaron, O., On k-factor-critical graphs, Discuss Math - Graph Theory, 16, 41-51 (1996) · Zbl 0865.05061 |
| [90] | Ferland, K., On the toughness of some generalized Petersen graphs, Ars Combinatoria, 36, 65-88 (1993) · Zbl 0793.05083 |
| [91] | Ferland, K., Toughness of generalized Petersen graphs, Ars Combinatoria, 66, 49-63 (2003) · Zbl 1072.05542 |
| [92] | Fleischner, H., The square of every two-connected graph is hamiltonian, J. Comb. Theory - Ser. B, 16, 29-34 (1974) · Zbl 0256.05121 |
| [93] | Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco, CA, 1979 · Zbl 0411.68039 |
| [94] | Gerlach, T., Toughness and hamiltonicity of a class of planar graphs, Discrete Math, 286, 61-65 (2004) · Zbl 1048.05053 |
| [95] | Goddard, W., Measures of vulnerability - the integrity family, NETWORKS, 24, 207-213 (1994) · Zbl 0824.90133 |
| [96] | Goddard, W., The toughness of cubic graphs, Graphs and Combin, 12, 17-22 (1996) · Zbl 0846.05049 |
| [97] | Goddard, W.; Plummer, M. D.; Swart, H., Maximum and minimum toughness of graphs of small genus, Discrete Math, 167/168, 329-339 (1997) · Zbl 0874.05036 |
| [98] | Goddard, W.; Swart, H. C., On the toughness of a graph, Quaestiones Math, 13, 217-232 (1990) · Zbl 0708.05035 |
| [99] | Goddard, W., Swart, H.: On some extremal problems in connectivity. In: Alavi, Y., Chartrand, G., Oellermann, O.R., Schwenk, A.J. (eds.), Graph Theory, Combinatorics, and Applications - Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. John Wiley & Sons, Inc., New York, pp 535-551, 1991 · Zbl 0840.05043 |
| [100] | Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980 · Zbl 0541.05054 |
| [101] | Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin, 1988 · Zbl 0634.05001 |
| [102] | Grünbaum, B.; Walther, H., Shortness exponents of families of graphs, J. Combin. Theory - Ser. B, 14, 364-385 (1973) · Zbl 0263.05103 |
| [103] | Häggkvist, R., On the structure of non-hamiltonian graphs I, Combinat. Prob. and Comp, 1, 27-34 (1992) · Zbl 0794.05069 |
| [104] | Häggkvist, R.; Nicoghossian, G. G., A remark on hamiltonian cycles, J. Combin. Theory - Ser. B, 30, 118-120 (1981) · Zbl 0462.05046 |
| [105] | Harant, J., Toughness and nonhamiltonicity of polyhedral graphs, Discrete Math, 113, 249-253 (1993) · Zbl 0771.05057 |
| [106] | Harant, J.; Owens, P. J., Nonhamiltonian 5/4-tough maximal planar graphs, Discrete Math, 113, 301-305 (1993) · Zbl 0838.05043 |
| [107] | Hoa, V. D., A sharp lower bound for the circumference of 1-tough graphs with large degree sums, J. Graph. Theory, 20, 137-140 (1995) · Zbl 0833.05050 |
| [108] | Hoa, V. D., A remark on hamiltonian cycles, Math. Nachr, 157, 163-168 (1992) · Zbl 0774.05062 |
| [109] | Hoa, V. D., On the length of longest dominating cycles in graphs, Discrete Math, 121, 211-222 (1993) · Zbl 0783.05066 |
| [110] | Hoa, V. D., Long cycles and neigborhood unions in 1-tough graphs with large degree sums, Discuss Math - Graph Theory, 18, 5-13 (1998) · Zbl 0913.05064 |
| [111] | Hoàng, C. T., Hamiltonian degree conditions for tough graphs, Discrete Math, 142, 121-139 (1995) · Zbl 0854.05071 |
| [112] | Jackson, B.: Concerning the circumference of certain families of graphs, Updated Contributions to the Twente Workshop on Hamiltonian Graph Theory, Technical report, University of Twente, The Netherlands, 87-94 (1992) |
| [113] | Jackson, B.: Hamilton cycles in 7-connected line graphs. Preprint, 1989 |
| [114] | Jackson, B.; Katerinis, P., A characterization of 3/2-tough cubic graphs, Ars Combinatoria, 38, 145-148 (1994) · Zbl 0815.05053 |
| [115] | Jackson, B.; Wormald, N. C., Longest cycles in 3-connected planar graphs, J. Combin Theory - Ser. B, 54, 291-321 (1992) · Zbl 0696.05031 |
| [116] | Jung, H. A., On maximal circuits in finite graphs, Ann. Discrete Math, 3, 129-144 (1987) · Zbl 0399.05039 |
| [117] | Jung, H.A., Kyaw, S., Wei, B.: Almost-hamiltonian graphs, In : Contemporary methods in graph theory. Bibligr. Inst. Mannheim, 409-427 (1990) · Zbl 0731.05032 |
| [118] | Jung, H. A.; Wittmann, P., Longest cycles in tough graphs, J. Graph Theory, 31, 107-127 (1999) · Zbl 0927.05042 |
| [119] | Katerinis, P., Toughness of graphs and the existence of factors, Discrete Math, 80, 81-92 (1990) · Zbl 0739.05047 |
| [120] | Katerinis, P., Two sufficient conditions for a 2-factor in a bipartite graph, J. Graph Theory, 11, 1-6 (1987) · Zbl 0651.05053 |
| [121] | Katona, G. Y., Toughness and edge-toughness, Discrete Math, 164, 187-196 (1997) · Zbl 0874.05035 |
| [122] | Katona, G. Y., Properties of edge-tough graphs, Graphs and Combin, 15, 315-325 (1999) · Zbl 0931.05067 |
| [123] | Kelly, J. B.; Kelly, L. M., Paths and circuits in critical graphs, Amer. J. Math, 76, 786-792 (1954) · Zbl 0056.16902 |
| [124] | Kiel, J. M., Finding Hamiltonian circuits in interval graphs, Inf. Process. Lett, 20, 201-206 (1985) · Zbl 0578.68053 |
| [125] | Kratsch, D.: Private communication |
| [126] | Kratsch, D.; Lehel, J.; Müller, H., Toughness, hamiltonicity and split graphs, Discrete Math, 150, 231-245 (1996) · Zbl 0855.05079 |
| [127] | Lesniak, L.: Neighborhood unions and graphical properties. In: Alavi, Y., Chartrand, G., Oellermann, O.R., Schwenk, A.J. (eds.), Graph Theory, Combinatorics, and Applications - Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. John Wiley & Sons, Inc., New York, pp 783-800, 1991 · Zbl 0840.05057 |
| [128] | Li, H., Circumferences in 1-tough graphs, Discrete Math, 146, 325-328 (1995) · Zbl 0856.05057 |
| [129] | Li, J., Cycles containing many vertices of subsets in 1-tough graphs with large degree sums, Ars Combinatoria, 48, 195-212 (1998) · Zbl 0963.05074 |
| [130] | Linial, N., A lower bound on the circumference of a graph, Discrete Math, 15, 297-300 (1976) · Zbl 0344.05139 |
| [131] | Liu, G.; Yu, Q., k-factors and extendability with prescribed components, Congr. Numer, 139, 77-88 (1999) · Zbl 0961.05057 |
| [132] | Lovász, L., Plummer, M.D.: Matching Theory. Ann. Discrete Math 29 North-Holland, Amsterdam, 1986 · Zbl 0618.05001 |
| [133] | Lubotsky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs. Combinatorica, 8, 261-277 (1988) · Zbl 0661.05035 |
| [134] | Margulis, G. A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators (Russian), Problemy Peredachi Informatsii, 24, 51-60 (1988) · Zbl 0708.05030 |
| [135] | Matthews, M. M.; Sumner, D. P., Hamiltonian results in K 1,3-free graphs, J. Graph Theory, 1, 139-146 (1984) · Zbl 0536.05047 |
| [136] | Moon, J.; Moser, L., On hamiltonian bipartite graphs, Israel J. Math, 1, 163-165 (1963) · Zbl 0119.38806 |
| [137] | Mycielski, J., Sur le coloriage des graphes, Colloq. Math, 3, 161-162 (1955) · Zbl 0064.17805 |
| [138] | Nash-Williams, C.St.J.A.: Hamiltonian circuits in graphs and digraphs. In: Chartrand, G., Kapoor, S.G. (eds.), The Many Facets of Graph Theory. Springer, Berlin, pp 237-243, 1969 · Zbl 0195.25902 |
| [139] | Nash-Williams, C.St.J.A.: Edge-disjoint hamiltonian circuits in graphs with vertices of large valency. Studies in Pure Mathematics. Academic Press, London, pp 157-183, 1971 · Zbl 0223.05123 |
| [140] | Nishizeki, T., A 1-tough non hamiltonian maximal planar graph, Discrete Math, 30, 305-307 (1980) · Zbl 0442.05046 |
| [141] | Ore, O., Note on hamikonian circuits, Amer. Math. Monthly, 67, 55 (1960) · Zbl 0089.39505 |
| [142] | Owens, P. J., Nonhamiltonian maximal planar graphs with high toughness, Tatra Mountains Math. Publ, 18, 89-103 (1999) · Zbl 0951.05067 |
| [143] | Piazza, B.; Ringeisen, R.; Stueckle, S., On the vulnerability of cycle permutation graphs, Ars Combinatoria, 29, 289-296 (1990) · Zbl 0743.05068 |
| [144] | Plummer, M. D., Toughness and matching extension in graphs, Discrete Math, 72, 311-320 (1988) · Zbl 0683.05034 |
| [145] | Plummer, M. D., A note on toughness and tough components, Congr. Numer, 125, 179-192 (1997) · Zbl 0894.05023 |
| [146] | Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory - Ser. B, 70, 217-224 (1997) · Zbl 0872.05032 |
| [147] | Schiermeyer, I.: Hamilton cycles in path-tough graphs, Updated Contributions to the Twente Workshop on Hamiltonian Graph Theory, Technical report, University of Twente, The Netherlands, pp 97-99, 1992 |
| [148] | Schmeichel, E. F.; Bloom, G. S., Connectivity, genus, and the number of components in vertex-deleted subgraphs, J. Combin. Theory - Ser. B, 27, 198-201 (1979) · Zbl 0346.05104 |
| [149] | Shi, M.; Yuan, X.; Cai, M.; Favaron, O., (3,k)-factor-critical graphs and toughness, Graphs and Combin, 15, 463-471 (1999) · Zbl 0939.05069 |
| [150] | Skupień, Z.: An improvement of Jung’s condition for hamiltonicity, 30. Internat. Wissenschafl. Koll. Technische Hochschule Ilmenau (GDR), Heft 5, 111-113 (1985) · Zbl 0594.05044 |
| [151] | Thomassen, C., Long cycles in digraphs, Proc. London Math. Soc., 42, 231-251 (1981) · Zbl 0454.05029 |
| [152] | Thomassen, C., Reflections on graph theory, J. Graph Theory, 10, 309-324 (1986) · Zbl 0614.05050 |
| [153] | Tkáč, M., On the shortness exponent of 1-tough, maximal planar graphs, Discrete Math, 154, 321-328 (1996) · Zbl 0852.05055 |
| [154] | Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403 |
| [155] | Veldman, H. J., Existence of dominating cycles and paths, Discrete Math, 43, 281-296 (1983) · Zbl 0503.05037 |
| [156] | Watkins, M. E., A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory, 6, 152-164 (1969) · Zbl 0175.50303 |
| [157] | Wei, B., A generalization of a result of Bauer and Schmeichel, Graphs and Combin, 9, 383-389 (1993) · Zbl 0791.05071 |
| [158] | Win, S., On a connection between the existence of k-trees and the toughness of a graph, Graphs and Combin, 5, 201-205 (1989) · Zbl 0673.05054 |
| [159] | Woeginger, G. J., The toughness of split graphs, Discrete Math, 190, 295-297 (1998) · Zbl 0955.05103 |
| [160] | Woodall, D. R., The binding number of a graph and its Anderson number, J. Combin. Theory - Ser B, 15, 225-255 (1973) · Zbl 0253.05139 |
| [161] | Zhan, S., On hamiltonian line graphs and connectivity, Discrete Math, 89, 89-95 (1991) · Zbl 0727.05037 |
| [162] | Zykov, A. A., On some properties of linear complexes (Russian), Mat. Sb, 24, 163-188 (1949) · Zbl 0033.02602 |
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.
