×

Parameterized binding numbers and degree sequence theorems. (English) Zbl 07833074

Summary: We define an extension of the standard binding number of a graph which introduces parameters into the computation. We call the result a parameterized binding number. This extension is motivated by a number of theorems that use bounds on the order of neighbor sets of vertices to determine the existence of cycles or factors within the graph. We demonstrate how this extended binding number can be integrated into such theorems. Additionally, we present theorems that provide sufficient conditions on the degree sequence of a graph which guarantees a prescribed lower bound on parameterized binding numbers. These degree sequence theorems are shown to be best possible in a certain sense. Finally, we show how these degree conditions can be combined with known theorems to produce sufficient conditions which guarantee certain cycles or factors within the graph.

MSC:

05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C07 Vertex degrees
05C92 Chemical graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
Full Text: DOI

References:

[1] D. Bauer, H. J. Broersma, J. van den Heuvel, N. Kahl, A. Nevo, E. Schmeichel, D. R. Woodall, M. Yatauro, Best monotone degree conditions for graph properties: A survey, Graphs Combin. 31 (2015) 1-22. · Zbl 1306.05032
[2] D. Bauer, N. Kahl, E. Schmeichel, M. Yatauro, Best monotone degree conditions for binding number, Discrete Math. 311 (2011) 2037-2043. · Zbl 1283.05139
[3] V. Chv átal, On Hamilton’s ideals, J. Combin. Theory Ser. B. 12 (1972) 163-168. · Zbl 0213.50803
[4] R. Shi, The binding number of a graph and its triangle, Acta Math. Appl. Sin. Engl. Ser. 2 (1985) 79-86. · Zbl 0638.05047
[5] D. Woodall, The binding number of a graph and its Anderson number, J. Combin. Theory Ser. B. 15 (1973) 225-255. · Zbl 0253.05139
[6] D. Woodall, k-factors and neighborhoods of independent sets in graphs, J. London Math. Soc. s2-41 (1990) 385-392. · Zbl 0659.05070
[7] D. Woodall, Triangles and neighborhoods of independent sets in graphs, J. Combin. Theory Ser. B. 80 (2000) 122-129. · Zbl 1023.05087
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.