Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Toughness in Graphs – A Survey

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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!

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  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)

    Google Scholar 

  2. Alon, N.: Tough ramsey graphs without short cycles. Journal of Algebraic Combinatorics 4, 189–195 (1995)

    Google Scholar 

  3. Balakrishnan, R., Paulraja, P.: Chordal graphs and some of their derived graphs. Congr Numer 53, 71–74 (1986)

    Google Scholar 

  4. Barefoot, C.A., Entringer, R., Swart, H.: Vulnerability in graphs - a comparative survey. J. Combin. Math. Combin. Comput 1, 13–22 (1987)

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  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)

  8. Bauer, D., Broersma, H.J., Li,R., Veldman, H.J.: A generalization of a result of Häggkvist and Nicoghossian. J. Combin. Theory – Ser B 47, 237–243 (1989)

    Google Scholar 

  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)

    Google Scholar 

  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)

  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)

  12. Bauer, D., Broersma, H.J., Veldman, H.J.: On generalizing a theorem of Jung. Ars Combinatoria 40, 207–218 (1995)

    Google Scholar 

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

    Google Scholar 

  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)

    Google Scholar 

  16. Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math 28, 191–195 (1990)

    Google Scholar 

  17. Bauer, D., van den Heuvel, J., Morgana, A., Schmeichel, E.: The complexity of recognizing tough cubic graphs. Discrete Appl. Math 79, 35–44 (1997)

    Google Scholar 

  18. Bauer, D., van den Heuvel, J., Morgana, A., Schmeichel, E.: The complexity of toughness in regular graphs. Congr. Numer 130, 47–61 (1998)

    Google Scholar 

  19. Bauer, D., van den Heuvel, J., Schmeichel, E.: Toughness and triangle-free graphs. J Combin. Theory – Ser. B 65, 208–221 (1995)

    Google Scholar 

  20. Bauer, D., van den Heuvel, J., Schmeichel, E.: 2-Factors in triangle-free graphs. J Graph Theory 21, 405–412 (1996)

    Google Scholar 

  21. Bauer, D., Jung, H.A., Schmeichel, E.: On 2-connected graphs with small circumference. J Combin. Inform. Systems Sci 15, 16–24 (1990)

    Google Scholar 

  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)

    Google Scholar 

  23. Bauer, D., Morgana, A., Schmeichel, E.: A simple proof of a theorem of Jung. Discrete Math 79, 147–152 (1990)

    Google Scholar 

  24. Bauer, D., Morgana, A., Schmeichel, E.: On the complexity of recognizing tough graphs. Discrete Math 124, 13–17 (1994)

    Google Scholar 

  25. Bauer, D., Morgana, A., Schmeichel, E., Veldman, H.J.: Long cycles in graphs with large degree sums. Discrete Math 79, 59–70 (1989/90)

    Google Scholar 

  26. Bauer, D., Niessen, T., Schmeichel, E.: Toughness, minimum degree, and spanning cubic subgraphs. J Graph Theory 45, 119–141 (2004)

    Google Scholar 

  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)

  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 2nd China-USA Graph Theory Conference. SIAM pp 20–25 (1991)

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

    Google Scholar 

  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.

  31. Bauer, D., Schmeichel, E., Veldman, H.J.: A note on dominating cycles in 2-connected graphs. Discrete Math 155, 13–18 (1996)

    Google Scholar 

  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)

  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)

    Google Scholar 

  35. Berge, C.: Two theorems in graph theory. Proc. Nat. Acad. Sci. USA 43, 842–844 (1957)

    Google Scholar 

  36. Bermond, J.C.: On Hamiltonian walks. Congr Numer 15, 41–51 (1976)

    Google Scholar 

  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

  38. Bertossi, A.A.: The edge hamiltonian path problem is NP-complete. Inform Process Lett 13, 157–159 (1981)

    Google Scholar 

  39. Bigalke, A., Jung, H.A.: Über Hamiltonische Kreise und unabhängige Ecken in Graphen. Monatsh Math 88, 195–210 (1979)

    Google Scholar 

  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)

    Google Scholar 

  41. Böhme, T., Harant, J., Tkáč, M.: More than 1-tough chordal planar graphs are hamiltonian. J. Graph Theory 32, 405–410 (1999)

    Google Scholar 

  42. Bondy, J.A.: Large cycles in graphs. Discrete Math 1, 121–131 (1971)

    Google Scholar 

  43. Bondy, J.A.: Pancyclic graphs I. J. Combin. Theory – Ser. B 11, 80–84 (1971)

  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)

    Google Scholar 

  47. Brandt, S.: Cycles and paths in triangle-free graphs. Algorithms Combin 14, 32–42 (1997)

    Google Scholar 

  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

  50. Brandt, S., Faudree, R., Goddard, W.: Weakly pancyclic graphs. J. Graph Theory 27, 141–176 (1998)

    Google Scholar 

  51. Brandt, S., Veldman, H.J.: Degree sums for edges and cycle lengths in graphs. J. Graph Theory 25, 253–256 (1997)

    Google Scholar 

  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

  53. Broersma, H.J., Engbers, E., Trommel, H.: Various results on the toughness of graphs. NETWORKS 33, 233–238 (1999)

    Google Scholar 

  54. Broersma, H.J., van den Heuvel, J., Jung, H.A., Veldman, H.J.: Long paths and cycles in tough graphs. Graphs and Combin 9, 3–17 (1993)

    Google Scholar 

  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., van den Heuvel, J., Veldman, H.J.: Long cycles, degree sums and neighborhood unions. Discrete Math 121, 25–35 (1993)

    Google Scholar 

  57. Broersma, H.J., Xiong, L., Yoshimoto, K.: Toughness and hamiltonicity in k-trees, To appear in Discrete Math.

  58. Brouwer, A.E.: Toughness and spectrum of a graph. Linear Algebra Appl 226, 267–271 (1995)

    Google Scholar 

  59. Cai, M., Favaron, O., Li, H.: (2,k)-factor-critical graphs and toughness. Graphs and Combin 15, 137–142 (1999)

    Google Scholar 

  60. Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall, London, 1996

  61. Chen, C.: Toughness of graphs and k-factors with given properties. Ars Combinatoria 34, 55–64 (1992)

    Google Scholar 

  62. Chen, C.: Toughness of graphs and [2,b]-factors. Graphs and Combin 10, 97–100 (1994)

    Google Scholar 

  63. Chen, G., Jacobson, M.S., Kézdy, A.E., Lehel, J.: Tough enough chordal graphs are hamiltonian. NETWORKS 31, 29–38 (1998)

    Google Scholar 

  64. Chen, G., Yu, X.: Long cycles in 3-connected graphs. J Combin Theory – Ser B 86, 80–99 (2002)

    Google Scholar 

  65. Chvátal, V.: On Hamilton's ideals. J Combin. Theory – Ser. B 12, 163–168 (1972)

  66. Chvátal, V.: Private communication

  67. Chvátal, V.: Tough graphs and hamiltonian circuits. Discrete Math 5, 215–228 (1973)

    Google Scholar 

  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

  69. Chvátal, V., Erdös, P.: A note on hamiltonian circuits. Discrete Math 2, 111–113 (1972)

    Google Scholar 

  70. Colbourn, C.J., Stewart, L.K.: Dominating cycles in series-parallel graphs. Ars Combinatoria 19a, 107–112 (1985)

    Google Scholar 

  71. Cunningham, W.H.: On submodular function minimization. Combinatorica 5, 185–192 (1985)

    Google Scholar 

  72. Dankelmann, P., Niessen, T., Schiermeyer, I.: On path-tough graphs. SIAM J Disc. Math 7, 571–584 (1994)

    Google Scholar 

  73. Deogun, J.S., Kratsch, D., Steiner, G.: 1-Tough cocomparability graphs are hamiltonian. Discrete Math 170, 99–106 (1997)

    Google Scholar 

  74. Descartes, B.: A three colour problem. Eureka 9, 21 (1947)

    Google Scholar 

  75. Dillencourt, M.B.: An upper bound on the shortness exponent of 1-tough maximal planar graphs. Discrete Math 90, 93–97 (1991)

    Google Scholar 

  76. Dillencourt, M.B.: On the toughness index of planar graphs. J Graph Theory 18, 103–107 (1994)

    Google Scholar 

  77. Dirac, G.A.: Some theorems on abstract graphs. Proc. London Math. Soc 2, 69–81 (1952)

    Google Scholar 

  78. Doty, L.: A large class of maximally tough graphs. OR Spektrum 13, 147–151 (1991)

    Google Scholar 

  79. Ellingham, N.N., Nam, Y., Voss, H.J.: Connected (g,f)-factors. J. Graph Theory 39, 62–75 (2002)

    Google Scholar 

  80. Ellingham, M.N., Zha, X.: Toughness, trees, and k-walks. J. Graph Theory 33, 125–137 (2000)

    Google Scholar 

  81. Enomoto, H.: Toughness and the existence of k-factors II. Graphs and Combin 2, 37–42 (1986)

    Google Scholar 

  82. Enomoto, H.: Toughness and the existence of k-factors III. Discrete Math 189, 277–282 (1998)

    Google Scholar 

  83. Enomoto, H., Hagita, M.: Toughness and the existence of k-factors IV. Discrete Math 216, 111–120 (2000)

    Google Scholar 

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

    Google Scholar 

  85. Erdös, P.: Graph theory and probability. Can. J. Math. 11, 34–38 (1959)

    Google Scholar 

  86. Fan, G.: New sufficient conditions for cycles in graphs. J. Combin. Theory – Ser B 37, 221–227 (1984)

    Google Scholar 

  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)

    Google Scholar 

  88. Faudree, R., Gould, R., Jacobson, M., Lesniak, L., Saito, A.: Toughness, degrees and 2-factors. Discrete Math 286, 245–249 (2004)

    Google Scholar 

  89. Favaron, O.: On k-factor-critical graphs. Discuss Math - Graph Theory 16, 41–51 (1996)

    Google Scholar 

  90. Ferland, K.: On the toughness of some generalized Petersen graphs. Ars Combinatoria 36, 65–88 (1993)

    Google Scholar 

  91. Ferland, K.: Toughness of generalized Petersen graphs. Ars Combinatoria 66, 49–63 (2003)

    Google Scholar 

  92. Fleischner, H.: The square of every two-connected graph is hamiltonian. J. Comb. Theory – Ser. B 16, 29–34 (1974)

    Google Scholar 

  93. Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco, CA, 1979

  94. Gerlach, T.: Toughness and hamiltonicity of a class of planar graphs. Discrete Math 286, 61–65 (2004)

    Google Scholar 

  95. Goddard, W.: Measures of vulnerability - the integrity family. NETWORKS 24, 207–213 (1994)

    Google Scholar 

  96. Goddard, W.: The toughness of cubic graphs. Graphs and Combin 12, 17–22 (1996)

    Google Scholar 

  97. Goddard, W., Plummer, M.D., Swart, H.: Maximum and minimum toughness of graphs of small genus. Discrete Math 167/168, 329–339 (1997)

    Google Scholar 

  98. Goddard, W., Swart, H.C.: On the toughness of a graph. Quaestiones Math 13, 217–232 (1990)

    Google Scholar 

  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

  100. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980

  101. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin, 1988

  102. Grünbaum, B., Walther, H.: Shortness exponents of families of graphs. J. Combin. Theory – Ser. B 14, 364–385 (1973)

    Google Scholar 

  103. Häggkvist, R.: On the structure of non-hamiltonian graphs I. Combinat. Prob. and Comp 1, 27–34 (1992)

    Google Scholar 

  104. Häggkvist, R., Nicoghossian, G.G.: A remark on hamiltonian cycles. J. Combin. Theory – Ser. B 30, 118–120 (1981)

    Google Scholar 

  105. Harant, J.: Toughness and nonhamiltonicity of polyhedral graphs. Discrete Math 113, 249–253 (1993)

    Google Scholar 

  106. Harant, J., Owens, P.J.: Nonhamiltonian 5/4-tough maximal planar graphs. Discrete Math 113, 301–305 (1993)

    Google Scholar 

  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)

    Google Scholar 

  108. Hoa, V.D.: A remark on hamiltonian cycles. Math. Nachr 157, 163–168 (1992)

    Google Scholar 

  109. Hoa, V.D.: On the length of longest dominating cycles in graphs. Discrete Math 121, 211–222 (1993)

    Google Scholar 

  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)

    Google Scholar 

  111. Hoàng, C.T.: Hamiltonian degree conditions for tough graphs. Discrete Math 142, 121–139 (1995)

    Google Scholar 

  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)

    Google Scholar 

  115. Jackson, B., Wormald, N.C.: Longest cycles in 3-connected planar graphs. J. Combin Theory – Ser. B 54, 291–321 (1992)

    Google Scholar 

  116. Jung, H.A.: On maximal circuits in finite graphs. Ann. Discrete Math 3, 129–144 (1987)

    Google Scholar 

  117. Jung, H.A., Kyaw, S., Wei, B.: Almost-hamiltonian graphs, In : Contemporary methods in graph theory. Bibligr. Inst. Mannheim, 409–427 (1990)

  118. Jung, H.A., Wittmann, P.: Longest cycles in tough graphs. J. Graph Theory 31, 107–127 (1999)

    Google Scholar 

  119. Katerinis, P.: Toughness of graphs and the existence of factors. Discrete Math 80, 81–92 (1990)

    Google Scholar 

  120. Katerinis, P.: Two sufficient conditions for a 2-factor in a bipartite graph. J. Graph Theory 11, 1–6 (1987)

    Google Scholar 

  121. Katona, G.Y.: Toughness and edge-toughness. Discrete Math 164, 187–196 (1997)

    Google Scholar 

  122. Katona, G.Y.: Properties of edge-tough graphs. Graphs and Combin 15, 315–325 (1999)

    Google Scholar 

  123. Kelly, J.B., Kelly, L.M.: Paths and circuits in critical graphs. Amer. J. Math 76, 786–792 (1954)

    Google Scholar 

  124. Kiel, J.M.: Finding Hamiltonian circuits in interval graphs. Inf. Process. Lett 20, 201–206 (1985)

    Google Scholar 

  125. Kratsch, D.: Private communication

  126. Kratsch, D., Lehel, J., Müller, H.: Toughness, hamiltonicity and split graphs. Discrete Math 150, 231–245 (1996)

    Google Scholar 

  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

  128. Li, H.: Circumferences in 1-tough graphs. Discrete Math 146, 325–328 (1995)

    Google Scholar 

  129. Li, J.: Cycles containing many vertices of subsets in 1-tough graphs with large degree sums. Ars Combinatoria 48, 195–212 (1998)

    Google Scholar 

  130. Linial, N.: A lower bound on the circumference of a graph. Discrete Math 15, 297–300 (1976)

    Google Scholar 

  131. Liu, G., Yu, Q.: k-factors and extendability with prescribed components. Congr. Numer 139, 77–88 (1999)

    Google Scholar 

  132. Lovász, L., Plummer, M.D.: Matching Theory. Ann. Discrete Math 29 North-Holland, Amsterdam, 1986

  133. Lubotsky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988)

    Google Scholar 

  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)

    Google Scholar 

  135. Matthews, M.M., Sumner, D.P.: Hamiltonian results in K 1,3-free graphs. J. Graph Theory 1, 139–146 (1984)

    Google Scholar 

  136. Moon, J., Moser, L.: On hamiltonian bipartite graphs. Israel J. Math 1, 163–165 (1963)

    Google Scholar 

  137. Mycielski, J.: Sur le coloriage des graphes. Colloq. Math 3, 161–162 (1955)

    Google Scholar 

  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

  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

  140. Nishizeki, T.: A 1-tough non hamiltonian maximal planar graph. Discrete Math 30, 305–307 (1980)

    Google Scholar 

  141. Ore, O.: Note on hamikonian circuits. Amer. Math. Monthly 67, 55 (1960)

    Google Scholar 

  142. Owens, P.J.: Nonhamiltonian maximal planar graphs with high toughness. Tatra Mountains Math. Publ 18, 89–103 (1999)

    Google Scholar 

  143. Piazza, B., Ringeisen, R., Stueckle, S.: On the vulnerability of cycle permutation graphs. Ars Combinatoria 29, 289–296 (1990)

    Google Scholar 

  144. Plummer, M.D.: Toughness and matching extension in graphs. Discrete Math 72, 311–320 (1988)

    Google Scholar 

  145. Plummer, M.D.: A note on toughness and tough components. Congr. Numer 125, 179–192 (1997)

    Google Scholar 

  146. Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory – Ser. B 70, 217–224 (1997)

    Google Scholar 

  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)

    Google Scholar 

  149. Shi, M., Yuan, X., Cai, M., Favaron, O.: (3,k)-factor-critical graphs and toughness. Graphs and Combin 15, 463–471 (1999)

    Google Scholar 

  150. Skupień, Z.: An improvement of Jung's condition for hamiltonicity, 30. Internat. Wissenschafl. Koll. Technische Hochschule Ilmenau (GDR), Heft 5, 111–113 (1985)

  151. Thomassen, C.: Long cycles in digraphs. Proc. London Math. Soc. 42, 231–251 (1981)

    Google Scholar 

  152. Thomassen, C.: Reflections on graph theory. J. Graph Theory 10, 309–324 (1986)

    Google Scholar 

  153. Tkáč, M.: On the shortness exponent of 1-tough, maximal planar graphs. Discrete Math 154, 321–328 (1996)

    Google Scholar 

  154. Tutte, W.T.: A theorem on planar graphs. Trans. Amer. Math. Soc. 82, 99–116 (1956)

    Google Scholar 

  155. Veldman, H.J.: Existence of dominating cycles and paths. Discrete Math 43, 281–296 (1983)

    Google Scholar 

  156. Watkins, M.E.: A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Combin. Theory 6, 152–164 (1969)

    Google Scholar 

  157. Wei, B.: A generalization of a result of Bauer and Schmeichel. Graphs and Combin 9, 383–389 (1993)

    Google Scholar 

  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)

    Google Scholar 

  159. Woeginger, G.J.: The toughness of split graphs. Discrete Math 190, 295–297 (1998)

    Google Scholar 

  160. Woodall, D.R.: The binding number of a graph and its Anderson number. J. Combin. Theory – Ser B 15, 225–255 (1973)

    Google Scholar 

  161. Zhan, S.: On hamiltonian line graphs and connectivity. Discrete Math 89, 89–95 (1991)

    Google Scholar 

  162. Zykov, A.A.: On some properties of linear complexes (Russian). Mat. Sb 24, 163–188 (1949)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, NJ, 07030, USA

    Douglas Bauer

  2. Department of Computer Science, University of Durham, South Road, Durham, DH1 3LE, UK

    Hajo Broersma

  3. Department of Mathematics, San Jose State University, San Jose, CA, 95192, USA

    Edward Schmeichel

  4. Center for Combinatorics, Nankai University, Tianjin, 300071, P.R. China

    Hajo Broersma

Authors
  1. Douglas Bauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hajo Broersma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edward Schmeichel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Douglas Bauer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bauer, D., Broersma, H. & Schmeichel, E. Toughness in Graphs – A Survey. Graphs and Combinatorics 22, 1–35 (2006). https://doi.org/10.1007/s00373-006-0649-0

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-006-0649-0

Keywords

Search

Navigation