Best monotone degree conditions for binding number. (English) Zbl 1283.05139
Summary: We give sufficient conditions on the vertex degrees of a graph \(G\) to guarantee that \(G\) has binding number at least \(b\), for any given \(b>0\). Our conditions are best possible in exactly the same way that Chvátal’s well-known degree condition to guarantee a graph is Hamiltonian is best possible.
References:
| [1] | D. Bauer, H. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel, Degree sequences and the existence of \(k\); D. Bauer, H. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel, Degree sequences and the existence of \(k\) · Zbl 1256.05051 |
| [2] | D. Bauer, H. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel, Toughness and vertex degrees (submitted for publication).; D. Bauer, H. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel, Toughness and vertex degrees (submitted for publication). · Zbl 1259.05040 |
| [3] | Bauer, D.; Hakimi, S. L.; Kahl, N.; Schmeichel, E., Best monotone degree bounds for various graph parameters, Congr. Numer., 192, 75-83 (2008) · Zbl 1179.05055 |
| [4] | Bauer, D.; Hakimi, S. L.; Kahl, N.; Schmeichel, E., Sufficient degree conditions for \(k\)-edge-connectedness of a graph, Networks, 54, 2, 95-98 (2009) · Zbl 1207.05109 |
| [5] | Boesch, F., The strongest monotone degree condition for \(n\)-connectedness of a graph, J. Combin. Theory Ser. B, 16, 162-165 (1974) · Zbl 0262.05122 |
| [6] | Bondy, J. A., Properties of graphs with constraints on degrees, Studia Sci. Math. Hungar., 4, 473-475 (1969) · Zbl 0184.27702 |
| [7] | Bondy, J. A.; Chvátal, V., A method in graph theory, Discrete Math., 15, 111-135 (1976) · Zbl 0331.05138 |
| [8] | Chen, C., Binding number and toughness for matching extension, Discrete Math., 146, 303-306 (1995) · Zbl 0837.05092 |
| [9] | Chvátal, V., On Hamilton’s ideals, J. Combin. Theory Ser. B, 12, 163-168 (1972) · Zbl 0213.50803 |
| [10] | Cunningham, W. H., Computing the binding number of a graph, Discrete Appl. Math., 27, 283-285 (1990) · Zbl 0741.05068 |
| [11] | Hakimi, S. L.; Schmeichel, E., Pancyclic graphs and a conjecture of Bondy and Chvátal, J. Combin. Theory Ser. B, 17, 22-34 (1974) · Zbl 0279.05120 |
| [12] | Kano, M.; Tokushige, N., Binding numbers and \(f\)-factors of graphs, J. Combin. Theory Ser. B, 54, 2, 213-221 (1992) · Zbl 0772.05080 |
| [13] | Katerinis, P.; Woodall, D. R., Binding number of graphs and the existence of \(k\)-factors, Quart. J. Math. Oxford Ser., 38, 221-228 (1987) · Zbl 0639.05050 |
| [14] | Lyle, J.; Goddard, W., The binding number of a graph and its cliques, Discrete Appl. Math., 157, 3336-3340 (2009) · Zbl 1227.05206 |
| [15] | Robertshaw, A. M.; Woodall, D. R., Binding number conditions for matching extension, Discrete Math., 248, 169-179 (2002) · Zbl 0990.05102 |
| [16] | Shi, R., The binding number of a graph and its pancyclism, Acta Math. Appl. Sin. Engl. Ser., 3, 257-269 (1987) · Zbl 0626.05052 |
| [17] | West, D., Introduction to Graph Theory (2001), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey |
| [18] | 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 |
| [19] | Woodall, D. R., A sufficient condition for Hamiltonian circuits, J. Combin. Theory Ser. B, 25, 184-186 (1978) · Zbl 0322.05126 |
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.
