Binding numbers and $ [a,b]$-factors excluding a given <i>k</i>-factor

Zhou, Sizhong

doi:10.1016/j.crma.2011.08.007

Combinatorics

Binding numbers and

[a, b]

-factors excluding a given k-factor
[Nombre de liaisons et

[a, b]

-facteur excluant un k-facteur donné]

Présenté par : the Editorial Board

Zhou, Sizhong ¹

¹ School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, PR China

Comptes Rendus. Mathématique, Tome 349 (2011) no. 19-20, pp. 1021-1024.

Résumé
Abstract

Soit G un graphe dʼordre n et $a, b, k$ des entiers positifs tels que $1 \leq a \leq b$ . Un $[a, b]$ -facteur est défini comme étant un sous-graphe couvrant F de G tel que $a \leq d_{F} (x) \leq b$ pour tout $x \in 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 \geq \frac{{(a + b - 1)}^{2}}{b}$ , le nombre de liaisons $bind (G) \geq \frac{(a + b - 1) (n - 1)}{b n - (k + 1) (a + b - 1)}$ et $| N_{G} (X) | \geq \frac{(a - b) n + (k a + k b - 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) \cap E (Q) = \emptyset$ .

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 ⩽ d_{F} (x) ⩽ b$ for each $x \in 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 ⩾ \frac{{(a + b - 1)}^{2}}{b}$ , the binding number $bind (G) ⩾ \frac{(a + b - 1) (n - 1)}{b n - (k + 1) (a + b - 1)}$ , and $| N_{G} (X) | ⩾ \frac{(a - 1) n + (k a + k b - 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) \cap E (Q) = \emptyset$ .

Reçu le : 2011-05-25
Accepté le : 2011-08-16
Publié le : 2011-09-15

DOI : 10.1016/j.crma.2011.08.007

Affiliations des auteurs :

Zhou, Sizhong ¹

¹ 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, Tome 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/

Bibliographie
Cité par

[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

Cité par 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.