{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:59:41Z","timestamp":1778497181040,"version":"3.51.4"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,26]],"date-time":"2014-09-26T00:00:00Z","timestamp":1411689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s00373-014-1465-6","type":"journal-article","created":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T14:33:58Z","timestamp":1411655638000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Best Monotone Degree Conditions for Graph Properties: A Survey"],"prefix":"10.1007","volume":"31","author":[{"given":"D.","family":"Bauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. J.","family":"Broersma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"van den Heuvel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Kahl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Nevo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Schmeichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. R.","family":"Woodall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Yatauro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,26]]},"reference":[{"key":"1465_CR1","volume-title":"The Probabilistic Method","author":"N Alon","year":"1992","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (1992)"},{"key":"1465_CR2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0095-8956(71)90041-4","volume":"10","author":"I Anderson","year":"1971","unstructured":"Anderson, I.: Perfect matchings of a graph. J. Combin. Theory Ser. B 10, 183\u2013186 (1971)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00373-011-1044-z","volume":"28","author":"D Bauer","year":"2012","unstructured":"Bauer, D., Broersma, H.J., van den Heuvel, J., Kahl, N., Schmeichel, E.: Degree sequences and the existence of $$k$$ k -factors. Graphs Combin. 28, 149\u2013166 (2012)","journal-title":"Graphs Combin."},{"key":"1465_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1002\/jgt.21639","volume":"72","author":"D Bauer","year":"2013","unstructured":"Bauer, D., Broersma, H.J., van den Heuvel, J., Kahl, N., Schmeichel, E.: Toughness and vertex degrees. J. Graph Theory 72, 209\u2013219 (2013)","journal-title":"J. Graph Theory"},{"key":"1465_CR5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0166-218X(99)00141-9","volume":"99","author":"D Bauer","year":"2000","unstructured":"Bauer, D., Broersma, H.J., Veldman, H.J.: Not every 2-tough graph is hamiltonian. Discrete Appl. Math. 99, 317\u2013321 (2000)","journal-title":"Discrete Appl. Math."},{"key":"1465_CR6","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/net.20299","volume":"54","author":"D Bauer","year":"2009","unstructured":"Bauer, D., Hakimi, S.L., Kahl, N., Schmeichel, E.: Sufficient degree conditions for $$k$$ k -edge-connectedness of a graph. Networks 54, 95\u201398 (2009)","journal-title":"Networks"},{"key":"1465_CR7","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","volume":"28","author":"D Bauer","year":"1990","unstructured":"Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math. 28, 191\u2013195 (1990)","journal-title":"Discrete Appl. Math."},{"key":"1465_CR8","first-page":"87","volume":"216","author":"D Bauer","year":"2013","unstructured":"Bauer, D., Kahl, N., Schmeichel, E., Woodall, D.R., Yatauro, M.: Improving theorems in a best monotone sense. Congr. Numer. 216, 87\u201395 (2013)","journal-title":"Congr. Numer."},{"key":"1465_CR9","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.dam.2012.08.007","volume":"165","author":"D Bauer","year":"2014","unstructured":"Bauer, D., Kahl, N., Schmeichel, E., Woodall, D.R., Yatauro, M.: Toughness and binding number. Discrete Appl. Math. 165, 60\u201368 (2014)","journal-title":"Discrete Appl. Math."},{"key":"1465_CR10","doi-asserted-by":"crossref","first-page":"2037","DOI":"10.1016\/j.disc.2011.04.034","volume":"311","author":"D Bauer","year":"2011","unstructured":"Bauer, D., Kahl, N., Schmeichel, E., Yatauro, M.: Best monotone degree conditions for binding number. Discrete Math. 311, 2037\u20132043 (2011)","journal-title":"Discrete Math."},{"key":"1465_CR11","doi-asserted-by":"crossref","unstructured":"Bauer, D., Morgana, A., Schmeichel, E.F.: A simple proof of a theorem of Jung. Discrete Math. 79, 147\u2013152 (1989\/1990)","DOI":"10.1016\/0012-365X(90)90029-H"},{"key":"1465_CR12","unstructured":"Bauer, D., Nevo, A., Schmeichel, E.: Best monotone condition for 1-tough $$\\Rightarrow $$ \u21d2 2-factor (in preparation)"},{"key":"1465_CR13","unstructured":"Bauer, D., Nevo, A., Schmeichel, E.: Best monotone condition for 2-factor $$\\Rightarrow $$ \u21d2 1-tough (in preparation)"},{"key":"1465_CR14","unstructured":"Bauer, D., Nevo, A., Schmeichel, E.: Note on binding number, vertex degrees, and 1-factors (in preparation)"},{"key":"1465_CR15","unstructured":"Bauer, D., Nevo, A., Schmeichel, E.: Vertex arboricity and vertex degrees (in preparation)"},{"key":"1465_CR16","doi-asserted-by":"crossref","unstructured":"Bauer, D., Nevo, A., Schmeichel, E., Woodall, D.R., Yatauro, M.: Best monotone degree conditions for binding number and cycle structure. Discrete Appl. Math. (2014). doi: 10.1016\/j.dam.2013.12.014","DOI":"10.1016\/j.dam.2013.12.014"},{"key":"1465_CR17","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0095-8956(90)90133-K","volume":"48","author":"D Bauer","year":"1990","unstructured":"Bauer, D., Schmeichel, E.: Hamiltonian degree conditions which imply a graph is pancyclic. J. Combin. Theory Ser. B 48, 111\u2013116 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1002\/jgt.21633","volume":"71","author":"D Bauer","year":"2012","unstructured":"Bauer, D., Schmeichel, E.: Binding number, minimum degree, and cycle structure in graphs. J. Graph Theory 71, 219\u2013228 (2012)","journal-title":"J. Graph Theory"},{"key":"1465_CR19","volume-title":"Graphs and Hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)"},{"key":"1465_CR20","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0095-8956(74)90058-6","volume":"16","author":"F Boesch","year":"1974","unstructured":"Boesch, F.: The strongest monotone degree condition for $$n$$ n -connectedness of a graph. J. Combin. Theory Ser. B 16, 162\u2013165 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR21","first-page":"473","volume":"4","author":"JA Bondy","year":"1969","unstructured":"Bondy, J.A.: Properties of graphs with constraints on degrees. Studia Sci. Math. Hungar. 4, 473\u2013475 (1969)","journal-title":"Studia Sci. Math. Hungar."},{"key":"1465_CR22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(76)90078-9","volume":"15","author":"JA Bondy","year":"1976","unstructured":"Bondy, J.A., Chv\u00e1tal, V.: A method in graph theory. Discrete Math. 15, 111\u2013135 (1976)","journal-title":"Discrete Math."},{"key":"1465_CR23","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proc. Camb. Philos. Soc. 37, 194\u2013197 (1941)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"1465_CR24","unstructured":"Caro, Y.: New results on the independence number. Technical Report 05\u201379, Tel-Aviv University (1979)"},{"key":"1465_CR25","unstructured":"Chartrand, G., Harary, F.: Graphs with prescribed connectivities. In: Theory of Graphs, pp. 61\u201363. Academic Press, New York (1968)"},{"key":"1465_CR26","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1112\/S0025579300002369","volume":"15","author":"G Chartrand","year":"1968","unstructured":"Chartrand, G., Kapoor, S.F., Kronk, H.V.: A sufficient condition for $$n$$ n -connectedness of graphs. Mathematika 15, 51\u201352 (1968)","journal-title":"Mathematika"},{"key":"1465_CR27","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1112\/jlms\/s1-44.1.612","volume":"44","author":"G Chartrand","year":"1969","unstructured":"Chartrand, G., Kronk, H.V.: The point arboricity of planar graphs. J. Lond. Math. Soc. 44, 612\u2013616 (1969)","journal-title":"J. Lond. Math. Soc."},{"key":"1465_CR28","volume-title":"Graphs and Digraphs","author":"G Chartrand","year":"2011","unstructured":"Chartrand, G., Lesniak, L., Zhang, P.: Graphs and Digraphs, 5th edn. CRC Press, Boca Raton (2011)","edition":"5"},{"key":"1465_CR29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0012-365X(94)00175-5","volume":"146","author":"C Chen","year":"1995","unstructured":"Chen, C.: Binding number and toughness for matching extension. Discrete Math. 146, 303\u2013306 (1995)","journal-title":"Discrete Math."},{"key":"1465_CR30","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0095-8956(72)90020-2","volume":"12","author":"V Chv\u00e1tal","year":"1972","unstructured":"Chv\u00e1tal, V.: On Hamilton\u2019s ideals. J. Combin. Theory Ser. B 12, 163\u2013168 (1972)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR31","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Tough graphs and hamiltonian circuits. Discrete Math. 5, 215\u2013228 (1973)","journal-title":"Discrete Math."},{"key":"1465_CR32","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0166-218X(90)90072-K","volume":"27","author":"WH Cunningham","year":"1990","unstructured":"Cunningham, W.H.: Computing the binding number of a graph. Discrete Appl. Math. 27, 283\u2013285 (1990)","journal-title":"Discrete Appl. Math."},{"key":"1465_CR33","doi-asserted-by":"crossref","unstructured":"Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3) 2, 69\u201381 (1952)","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"1465_CR34","unstructured":"Egawa, Y., Enomoto, H.: Sufficient conditions for the existence of $$k$$ k -factors. In: Recent Studies in Graph Theory, pp. 96\u2013105. Vishwa, Gulbarga (1989)"},{"key":"1465_CR35","unstructured":"Gallai, T.: On directed paths and circuits. In: Theory of Graphs, pp. 115\u2013118. Academic Press, New York (1968)"},{"key":"1465_CR36","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1137\/0402007","volume":"2","author":"SL Hakimi","year":"1989","unstructured":"Hakimi, S.L., Schmeichel, E.F.: A note on the vertex arboricity of a graph. SIAM J. Discrete Math. 2, 64\u201367 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"1465_CR37","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","volume":"17","author":"GH Hardy","year":"1918","unstructured":"Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17, 75\u2013115 (1918)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1465_CR38","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0012-365X(93)E0214-O","volume":"142","author":"CT Ho\u00e0ng","year":"1995","unstructured":"Ho\u00e0ng, C.T.: Hamiltonian degree conditions for tough graphs. Discrete Math. 142, 121\u2013139 (1995)","journal-title":"Discrete Math."},{"key":"1465_CR39","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0167-5060(08)70503-X","volume":"3","author":"HA Jung","year":"1978","unstructured":"Jung, H.A.: On maximal circuits in finite graphs. Ann. Discrete Math. 3, 129\u2013144 (1978)","journal-title":"Ann. Discrete Math."},{"key":"1465_CR40","doi-asserted-by":"crossref","unstructured":"Kane, V.G., Mohanty, S.P.: Binding numbers, cycles and complete graphs. In: Combinatorics and Graph Theory. Lecture Notes in Mathematics, vol. 885, pp. 290\u2013296. Springer, Berlin (1981)","DOI":"10.1007\/BFb0092273"},{"key":"1465_CR41","unstructured":"Katerinis, P., Woodall, D.R.: Binding numbers of graphs and the existence of $$k$$ k -factors. Q. J. Math. Oxford Ser. (2) 38, 221\u2013228 (1987)"},{"key":"1465_CR42","unstructured":"Kriesell, M.: Degree sequences and edge connectivity. http:\/\/www.math.uni-hamburg.de\/research\/papers\/hbm\/hbm2007282 (2007) (preprint)"},{"key":"1465_CR43","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0021-9800(69)80043-8","volume":"7","author":"HV Kronk","year":"1969","unstructured":"Kronk, H.V.: A note on $$k$$ k -path hamiltonian graphs. J. Combin. Theory 7, 104\u2013106 (1969)","journal-title":"J. Combin. Theory"},{"key":"1465_CR44","unstructured":"Las Vergnas, M.: Probl\u00e8mes de Couplages et Probl\u00e8mes Hamiltoniens en Th\u00e9orie des Graphes. PhD Thesis, Universit\u00e9 Paris VI\u2014Pierre et Marie Curie (1972)"},{"key":"1465_CR45","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(76)90059-5","volume":"14","author":"L Lesniak","year":"1976","unstructured":"Lesniak, L.: On $$n$$ n -hamiltonian graphs. Discrete Math. 14, 165\u2013169 (1976)","journal-title":"Discrete Math."},{"key":"1465_CR46","doi-asserted-by":"crossref","first-page":"3336","DOI":"10.1016\/j.dam.2009.06.014","volume":"157","author":"J Lyle","year":"2009","unstructured":"Lyle, J., Goddard, W.: The binding number of a graph and its cliques. Discrete Appl. Math. 157, 3336\u20133340 (2009)","journal-title":"Discrete Appl. Math."},{"key":"1465_CR47","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(91)90357-8","volume":"90","author":"O Murphy","year":"1991","unstructured":"Murphy, O.: Lower bounds on the stability number of graphs computed in terms of degrees. Discrete Math. 90, 207\u2013211 (1991)","journal-title":"Discrete Math."},{"key":"1465_CR48","doi-asserted-by":"crossref","unstructured":"Nash-Williams, C.St.J.A.: Hamiltonian arcs and circuits. In: Recent Trends in Graph Theory. Lecture Notes in Mathematics, vol. 186, pp. 197\u2013210. Springer, Berlin (1971)","DOI":"10.1007\/BFb0059438"},{"key":"1465_CR49","unstructured":"P\u00f3sa, L.: A theorem concerning Hamilton lines. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 7, 225\u2013226 (1962)"},{"key":"1465_CR50","unstructured":"Rao, A.R.: The clique number of a graph with a given degree sequence. In: Proceedings of Symposium on Graph Theory. ISI Lecture Notes Series, vol. 4, pp. 251\u2013267. (1979)"},{"key":"1465_CR51","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1006\/jctb.2000.1974","volume":"80","author":"AM Robertshaw","year":"2000","unstructured":"Robertshaw, A.M., Woodall, D.R.: Triangles and neighbourhoods of independent sets in graphs. J. Combin. Theory Ser. B 80, 122\u2013129 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR52","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF02007670","volume":"3","author":"R Shi","year":"1987","unstructured":"Shi, R.: The binding number of a graph and its pancyclism. Acta Math. Appl. Sinica (English Series) 3, 257\u2013269 (1987)","journal-title":"Acta Math. Appl. Sinica (English Series)"},{"key":"1465_CR53","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G Szekeres","year":"1968","unstructured":"Szekeres, G., Wilf, H.S.: An inequality for the chromatic number of a graph. J. Combin. Theory 4, 1\u20133 (1968)","journal-title":"J. Combin. Theory"},{"key":"1465_CR54","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"1465_CR55","unstructured":"Wei, V.K.: A lower bound on the stability number of a simple graph. Technical Memorandum TM 81\u201311217-9, Bell Laboratories (1981)"},{"key":"1465_CR56","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"DJA Welsh","year":"1967","unstructured":"Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10, 85\u201386 (1967)","journal-title":"Comput. J."},{"key":"1465_CR57","volume-title":"Introduction to Graph Theory","author":"D West","year":"2001","unstructured":"West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"},{"key":"1465_CR58","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1112\/jlms\/s1-42.1.330","volume":"42","author":"HS Wilf","year":"1967","unstructured":"Wilf, H.S.: The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42, 330\u2013332 (1967)","journal-title":"J. Lond. Math. Soc."},{"key":"1465_CR59","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0095-8956(73)90038-5","volume":"15","author":"DR Woodall","year":"1973","unstructured":"Woodall, D.R.: The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15, 225\u2013255 (1973)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR60","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0095-8956(78)90037-0","volume":"25","author":"DR Woodall","year":"1978","unstructured":"Woodall, D.R.: A sufficient condition for hamiltonian circuits. J. Combin. Theory Ser. B 25, 184\u2013186 (1978)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1465_CR61","unstructured":"Woodall, D.R.: $$k$$ k -factors and neighbourhoods of independent sets in graphs. J. Lond. Math. Soc. (2) 41, 385\u2013392 (1990)"},{"key":"1465_CR62","unstructured":"Yin, J.-H., Guo, J.-Y.: Forcibly $$k$$ k -edge-connected graphic sequences (to appear, 2014)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1465-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-014-1465-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1465-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T14:59:38Z","timestamp":1559055578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-014-1465-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,26]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["1465"],"URL":"https:\/\/doi.org\/10.1007\/s00373-014-1465-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,26]]}}}