×

Best monotone degree conditions for graph properties: a survey. (English) Zbl 1306.05032

Summary: We survey sufficient degree conditions, for a variety of graph properties, that are best possible in the same sense that Chvátal’s well-known degree condition for Hamiltonicity is best possible.

MSC:

05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (1992) · Zbl 0767.05001
[2] Anderson, I.: Perfect matchings of a graph. J. Combin. Theory Ser. B 10, 183-186 (1971) · Zbl 0172.48904 · doi:10.1016/0095-8956(71)90041-4
[3] 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-166 (2012) · Zbl 1256.05051 · doi:10.1007/s00373-011-1044-z
[4] Bauer, D., Broersma, H.J., van den Heuvel, J., Kahl, N., Schmeichel, E.: Toughness and vertex degrees. J. Graph Theory 72, 209-219 (2013) · Zbl 1259.05040 · doi:10.1002/jgt.21639
[5] 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 · doi:10.1016/S0166-218X(99)00141-9
[6] Bauer, D., Hakimi, S.L., Kahl, N., Schmeichel, E.: Sufficient degree conditions for \[k\] k-edge-connectedness of a graph. Networks 54, 95-98 (2009) · Zbl 1207.05109 · doi:10.1002/net.20299
[7] Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math. 28, 191-195 (1990) · Zbl 0706.68052 · doi:10.1016/0166-218X(90)90001-S
[8] Bauer, D., Kahl, N., Schmeichel, E., Woodall, D.R., Yatauro, M.: Improving theorems in a best monotone sense. Congr. Numer. 216, 87-95 (2013) · Zbl 1293.05047
[9] Bauer, D., Kahl, N., Schmeichel, E., Woodall, D.R., Yatauro, M.: Toughness and binding number. Discrete Appl. Math. 165, 60-68 (2014) · Zbl 1288.05134 · doi:10.1016/j.dam.2012.08.007
[10] Bauer, D., Kahl, N., Schmeichel, E., Yatauro, M.: Best monotone degree conditions for binding number. Discrete Math. 311, 2037-2043 (2011) · Zbl 1283.05139 · doi:10.1016/j.disc.2011.04.034
[11] Bauer, D., Morgana, A., Schmeichel, E.F.: A simple proof of a theorem of Jung. Discrete Math. 79, 147-152 (1989/1990) · Zbl 0707.05045
[12] Bauer, D., Nevo, A., Schmeichel, E.: Best monotone condition for 1-tough \[\Rightarrow \]⇒ 2-factor (in preparation) · Zbl 1358.05064
[13] Bauer, D., Nevo, A., Schmeichel, E.: Best monotone condition for 2-factor \[\Rightarrow \]⇒ 1-tough (in preparation) · Zbl 1358.05064
[14] Bauer, D., Nevo, A., Schmeichel, E.: Note on binding number, vertex degrees, and 1-factors (in preparation) · Zbl 1351.05055
[15] Bauer, D., Nevo, A., Schmeichel, E.: Vertex arboricity and vertex degrees (in preparation) · Zbl 1351.05055
[16] 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 · Zbl 1320.05067
[17] Bauer, D., Schmeichel, E.: Hamiltonian degree conditions which imply a graph is pancyclic. J. Combin. Theory Ser. B 48, 111-116 (1990) · Zbl 0698.05047 · doi:10.1016/0095-8956(90)90133-K
[18] Bauer, D., Schmeichel, E.: Binding number, minimum degree, and cycle structure in graphs. J. Graph Theory 71, 219-228 (2012) · Zbl 1248.05105 · doi:10.1002/jgt.21633
[19] Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973) · Zbl 0254.05101
[20] Boesch, F.: The strongest monotone degree condition for \[n\] n-connectedness of a graph. J. Combin. Theory Ser. B 16, 162-165 (1974) · Zbl 0262.05122 · doi:10.1016/0095-8956(74)90058-6
[21] Bondy, J.A.: Properties of graphs with constraints on degrees. Studia Sci. Math. Hungar. 4, 473-475 (1969) · Zbl 0184.27702
[22] Bondy, J.A., Chvátal, V.: A method in graph theory. Discrete Math. 15, 111-135 (1976) · Zbl 0331.05138 · doi:10.1016/0012-365X(76)90078-9
[23] Brooks, R.L.: On colouring the nodes of a network. Proc. Camb. Philos. Soc. 37, 194-197 (1941) · JFM 67.0733.02 · doi:10.1017/S030500410002168X
[24] Caro, Y.: New results on the independence number. Technical Report 05-79, Tel-Aviv University (1979)
[25] Chartrand, G., Harary, F.: Graphs with prescribed connectivities. In: Theory of Graphs, pp. 61-63. Academic Press, New York (1968) · Zbl 0186.27503
[26] Chartrand, G., Kapoor, S.F., Kronk, H.V.: A sufficient condition for \[n\] n-connectedness of graphs. Mathematika 15, 51-52 (1968) · Zbl 0175.20703 · doi:10.1112/S0025579300002369
[27] Chartrand, G., Kronk, H.V.: The point arboricity of planar graphs. J. Lond. Math. Soc. 44, 612-616 (1969) · Zbl 0175.50505 · doi:10.1112/jlms/s1-44.1.612
[28] Chartrand, G., Lesniak, L., Zhang, P.: Graphs and Digraphs, 5th edn. CRC Press, Boca Raton (2011) · Zbl 1211.05001
[29] Chen, C.: Binding number and toughness for matching extension. Discrete Math. 146, 303-306 (1995) · Zbl 0837.05092 · doi:10.1016/0012-365X(94)00175-5
[30] Chvátal, V.: On Hamilton’s ideals. J. Combin. Theory Ser. B 12, 163-168 (1972) · Zbl 0213.50803 · doi:10.1016/0095-8956(72)90020-2
[31] Chvátal, V.: Tough graphs and hamiltonian circuits. Discrete Math. 5, 215-228 (1973) · Zbl 0256.05122 · doi:10.1016/0012-365X(73)90138-6
[32] Cunningham, W.H.: Computing the binding number of a graph. Discrete Appl. Math. 27, 283-285 (1990) · Zbl 0741.05068 · doi:10.1016/0166-218X(90)90072-K
[33] Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3) 2, 69-81 (1952) · Zbl 0047.17001
[34] Egawa, Y., Enomoto, H.: Sufficient conditions for the existence of \[k\] k-factors. In: Recent Studies in Graph Theory, pp. 96-105. Vishwa, Gulbarga (1989) · Zbl 1288.05134
[35] Gallai, T.: On directed paths and circuits. In: Theory of Graphs, pp. 115-118. Academic Press, New York (1968) · Zbl 0159.54403
[36] Hakimi, S.L., Schmeichel, E.F.: A note on the vertex arboricity of a graph. SIAM J. Discrete Math. 2, 64-67 (1989) · Zbl 0684.05028 · doi:10.1137/0402007
[37] Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17, 75-115 (1918) · JFM 46.0198.04 · doi:10.1112/plms/s2-17.1.75
[38] Hoàng, C.T.: Hamiltonian degree conditions for tough graphs. Discrete Math. 142, 121-139 (1995) · Zbl 0854.05071 · doi:10.1016/0012-365X(93)E0214-O
[39] Jung, H.A.: On maximal circuits in finite graphs. Ann. Discrete Math. 3, 129-144 (1978) · Zbl 0399.05039 · doi:10.1016/S0167-5060(08)70503-X
[40] 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-296. Springer, Berlin (1981) · Zbl 0706.68052
[41] Katerinis, P., Woodall, D.R.: Binding numbers of graphs and the existence of \[k\] k-factors. Q. J. Math. Oxford Ser. (2) 38, 221-228 (1987) · Zbl 0639.05050
[42] Kriesell, M.: Degree sequences and edge connectivity. http://www.math.uni-hamburg.de/research/papers/hbm/hbm2007282 (2007) (preprint) · Zbl 1388.05040
[43] Kronk, H.V.: A note on \[k\] k-path hamiltonian graphs. J. Combin. Theory 7, 104-106 (1969) · Zbl 0179.29105 · doi:10.1016/S0021-9800(69)80043-8
[44] Las Vergnas, M.: Problèmes de Couplages et Problèmes Hamiltoniens en Théorie des Graphes. PhD Thesis, Université Paris VI—Pierre et Marie Curie (1972)
[45] Lesniak, L.: On \[n\] n-hamiltonian graphs. Discrete Math. 14, 165-169 (1976) · Zbl 0316.05123 · doi:10.1016/0012-365X(76)90059-5
[46] Lyle, J., Goddard, W.: The binding number of a graph and its cliques. Discrete Appl. Math. 157, 3336-3340 (2009) · Zbl 1227.05206 · doi:10.1016/j.dam.2009.06.014
[47] Murphy, O.: Lower bounds on the stability number of graphs computed in terms of degrees. Discrete Math. 90, 207-211 (1991) · Zbl 0755.05055 · doi:10.1016/0012-365X(91)90357-8
[48] Nash-Williams, C.St.J.A.: Hamiltonian arcs and circuits. In: Recent Trends in Graph Theory. Lecture Notes in Mathematics, vol. 186, pp. 197-210. Springer, Berlin (1971) · Zbl 0223.05122
[49] Pósa, L.: A theorem concerning Hamilton lines. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7, 225-226 (1962) · Zbl 0114.40003
[50] 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-267. (1979)
[51] Robertshaw, A.M., Woodall, D.R.: Triangles and neighbourhoods of independent sets in graphs. J. Combin. Theory Ser. B 80, 122-129 (2000) · Zbl 1023.05087 · doi:10.1006/jctb.2000.1974
[52] Shi, R.: The binding number of a graph and its pancyclism. Acta Math. Appl. Sinica (English Series) 3, 257-269 (1987) · Zbl 0626.05052 · doi:10.1007/BF02007670
[53] Szekeres, G., Wilf, H.S.: An inequality for the chromatic number of a graph. J. Combin. Theory 4, 1-3 (1968) · Zbl 0171.44901 · doi:10.1016/S0021-9800(68)80081-X
[54] Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347-352 (1954) · Zbl 0055.17102 · doi:10.4153/CJM-1954-033-3
[55] Wei, V.K.: A lower bound on the stability number of a simple graph. Technical Memorandum TM 81-11217-9, Bell Laboratories (1981) · Zbl 0741.05068
[56] 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-86 (1967) · Zbl 0147.15206 · doi:10.1093/comjnl/10.1.85
[57] West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
[58] Wilf, H.S.: The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42, 330-332 (1967) · Zbl 0144.45202 · doi:10.1112/jlms/s1-42.1.330
[59] 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 · doi:10.1016/0095-8956(73)90038-5
[60] Woodall, D.R.: A sufficient condition for hamiltonian circuits. J. Combin. Theory Ser. B 25, 184-186 (1978) · Zbl 0322.05126 · doi:10.1016/0095-8956(78)90037-0
[61] Woodall, D.R.: \[k\] k-factors and neighbourhoods of independent sets in graphs. J. Lond. Math. Soc. (2) 41, 385-392 (1990) · Zbl 0659.05070
[62] Yin, J.-H., Guo, J.-Y.: Forcibly \[k\] k-edge-connected graphic sequences (to appear, 2014) · Zbl 0179.29105
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.