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 1ab. An [a,b]-factor of G is defined as a spanning subgraph F of G such that adF(x)b for each xV(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+b1)2b, the binding number bind(G)(a+b1)(n1)bn(k+1)(a+b1), and |NG(X)|(a1)n+(ka+kbk+1)|X|a+b1 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 1ab. Un [a,b]-facteur est défini comme étant un sous-graphe couvrant F de G tel que adF(x)b pour tout xV(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+b1)2b, le nombre de liaisons bind(G)(a+b1)(n1)bn(k+1)(a+b1) et |NG(X)|(ab)n+(ka+kbk+1)|X|a+b1 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)=.

Received:
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.