Combinatorics
Binding numbers and $[a,b]$-factors excluding a given k-factor
Comptes Rendus. Mathématique, Volume 349 (2011) no. 19-20, pp. 1021-1024.

Let G be a graph of order n, and let $a,b,k$ be nonnegative integers with $1⩽a⩽b$. An $[a,b]$-factor of G is defined as a spanning subgraph F of G such that $a⩽dF(x)⩽b$ for each $x∈V(G)$. If $a=b=k$, then an $[a,b]$-factor is called a k-factor. In this Note, it is proved that if G has a k-factor Q, $n⩾(a+b−1)2b$, the binding number $bind(G)⩾(a+b−1)(n−1)bn−(k+1)(a+b−1)$, and $|NG(X)|⩾(a−1)n+(ka+kb−k+1)|X|a+b−1$ for any nonempty independent subset X of $V(G)$, then G has an $[a,b]$-factor F such that $E(F)∩E(Q)=∅$.

Soit G un graphe dʼordre n et $a,b,k$ des entiers positifs tels que $1≤a≤b$. Un $[a,b]$-facteur est défini comme étant un sous-graphe couvrant F de G tel que $a≤dF(x)≤b$ pour tout $x∈V(G)$. Si $a=b=k$, alors un $[a,b]$-facteur est appelé k-facteur. Dans cette Note on démontre que si G a un k-facteur $Q,n≥(a+b−1)2b$, le nombre de liaisons $bind(G)≥(a+b−1)(n−1)bn−(k+1)(a+b−1)$ et $|NG(X)|≥(a−b)n+(ka+kb−k+1)|X|a+b−1$ pour tout sous-ensemble X non vide indépendant de $V(G)$, alors G a un $[a,b]$-facteur F tel que $E(F)∩E(Q)=∅$.

Accepted:
Published online:
DOI: 10.1016/j.crma.2011.08.007
Zhou, Sizhong 1

1 School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, PR China
@article{CRMATH_2011__349_19-20_1021_0,
author = {Zhou, Sizhong},
title = {Binding numbers and $[a,b]$-factors excluding a given \protect\emph{k}-factor},
journal = {Comptes Rendus. Math\'ematique},
pages = {1021--1024},
publisher = {Elsevier},
volume = {349},
number = {19-20},
year = {2011},
doi = {10.1016/j.crma.2011.08.007},
language = {en},
url = {http://www.numdam.org/articles/10.1016/j.crma.2011.08.007/}
}
TY  - JOUR
AU  - Zhou, Sizhong
TI  - Binding numbers and $[a,b]$-factors excluding a given k-factor
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 1021
EP  - 1024
VL  - 349
IS  - 19-20
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2011.08.007/
DO  - 10.1016/j.crma.2011.08.007
LA  - en
ID  - CRMATH_2011__349_19-20_1021_0
ER  - 
%0 Journal Article
%A Zhou, Sizhong
%T Binding numbers and $[a,b]$-factors excluding a given k-factor
%J Comptes Rendus. Mathématique
%D 2011
%P 1021-1024
%V 349
%N 19-20
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2011.08.007/
%R 10.1016/j.crma.2011.08.007
%G en
%F CRMATH_2011__349_19-20_1021_0
Zhou, Sizhong. Binding numbers and $[a,b]$-factors excluding a given k-factor. Comptes Rendus. Mathématique, Volume 349 (2011) no. 19-20, pp. 1021-1024. doi : 10.1016/j.crma.2011.08.007. http://www.numdam.org/articles/10.1016/j.crma.2011.08.007/

[1] Bondy, J.A.; Murty, U.S.R. Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1982

[2] Cai, J.; Liu, G. Binding number and Hamiltonian $(g,f)$-factors in graphs, J. Appl. Math. Comput., Volume 25 (2007), pp. 383-388

[3] Fourtounelli, O.; Katerinis, P. The existence of k-factors in squares of graphs, Discrete Math., Volume 310 (2010), pp. 3351-3358

[4] Katerinis, P.; Woodall, D.R. Binding numbers of graphs and the existence of k-factors, Quart. J. Math. Oxford, Volume 38 (1987), pp. 221-228

[5] Li, J.; Tang, S. Degree conditions for graphs to have $[a,b]$-factors excluding a given k-factor, J. Sys. Sci. & Math. Sci., Volume 29 (2009), pp. 1052-1060

[6] Lovász, L. Subgraphs with prescribed valencies, J. Combin. Theory, Volume 8 (1970), pp. 391-416

[7] Matsuda, H. Fan-type results for the existence of $[a,b]$-factors, Discrete Math., Volume 306 (2006), pp. 688-693

[8] Woodall, D.R. The binding number of a graph and its Anderson number, J. Combin. Theory Ser. B, Volume 15 (1973), pp. 225-255

[9] Zhou, S. Independence number, connectivity and $(a,b,k)$-critical graphs, Discrete Math., Volume 309 (2009), pp. 4144-4148

[10] Zhou, S.; Jiang, J. Notes on the binding numbers for $(a,b,k)$-critical graphs, Bull. Aust. Math. Soc., Volume 76 (2007), pp. 307-314

[11] Zhou, S.; Jiang, J. Toughness and $(a,b,k)$-critical graphs, Inform. Process. Lett., Volume 111 (2011), pp. 403-407

Cited by Sources:

This research was supported by Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (10KJB110003) and Jiangsu University of Science and Technology (2010SL101J, 2009SL154J), and was sponsored by Qing Lan Project of Jiangsu Province.