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

Sizhong Zhou

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

Sizhong Zhou ¹

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

Comptes Rendus. Mathématique, Volume 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 :

Sizhong Zhou ¹

¹ 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 = {Sizhong Zhou},
     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},
}

TY  - JOUR
AU  - Sizhong Zhou
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
DO  - 10.1016/j.crma.2011.08.007
LA  - en
ID  - CRMATH_2011__349_19-20_1021_0
ER  -

%0 Journal Article
%A Sizhong Zhou
%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
%R 10.1016/j.crma.2011.08.007
%G en
%F CRMATH_2011__349_19-20_1021_0

Sizhong Zhou. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.08.007/

Bibliographie
Cité par

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

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

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

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

[5] J. Li; S. Tang 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] L. Lovász Subgraphs with prescribed valencies, J. Combin. Theory, Volume 8 (1970), pp. 391-416

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

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

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

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

[11] S. Zhou; J. Jiang 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.

Commentaires - Politique