A New Sufficient Condition for a Graph To Be (g, f, n)-Critical

Zhou, Sizhong

Canadian mathematical bulletin, Tome 53 (2010) no. 2, pp. 378-384

Résumé

Let $G$ be a graph of order $p$ , let $a$ , $b$ , and $n$ be nonnegative integers with $1\,\le \,a\,<\,b$ , and let $g$ and $f$ be two integer-valued functions defined on $V\left( G \right)$ such that $a\,\le \,g\left( x \right)\,<\,f\left( x \right)\,\le \,b$ for all $x\,\in \,V\left( G \right)$ . A $\left( g,\,f \right)$ -factor of graph $G$ is a spanning subgraph $F$ of $G$ such that $g\left( x \right)\,\le \,{{d}_{F}}\left( x \right)\,\le \,f\left( x \right)$ for each $x\,\in \,V\left( F \right)$ . Then a graph $G$ is called $\left( g,\,f,\,n \right)$ -critical if after deleting any $n$ vertices of $G$ the remaining graph of $G$ has a $\left( g,\,f \right)$ -factor. The binding number $\text{bind}\left( G \right)$ of $G$ is the minimum value of $\left| {{N}_{G}}\left( X \right) \right|/\left| X \right|$ taken over all non-empty subsets $X$ of $V\left( G \right)$ such that ${{N}_{G}}\left( X \right)\,\ne \,V\left( G \right)$ . In this paper, it is proved that $G$ is a $\left( g,\,f,\,n \right)$ -critical graph if $$\text{bind}\left( G \right)\,>\,\frac{\left( a\,+\,b\,-\,1 \right)\left( p\,-\,1 \right)}{\left( a\,+\,1 \right)p\,-\,\left( a\,+b \right)\,-\,bn\,+\,2}\,\text{and}\,\text{p}\ge \,\frac{\left( a\,+\,b\,-\,1 \right)\left( a\,+\,b\,-2 \right)}{a\,+\,1}\,+\,\frac{bn}{a}.$$ Furthermore, it is shown that this result is best possible in some sense.

Détail

DOI : 10.4153/CMB-2010-034-8

Mots-clés : 05C70, graph, (g, f)-factor, (g, f, n)-critical graph, binding number

Bibliographie

[1] [1] Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications. American Elsevier Publishing, New York, 1976. Google Scholar

[2] [2] Chen, C., Binding number and minimum degree for [a, b]-factors. Syst. Sci. Math. Sci. 6(1993), no. 2, 179–185. Google Scholar

[3] [3] Egawa, Y. and Kano, M., Sufficient conditions for graphs to have (g, f)-factors. Discrete Math. 151(1996), no. 1–3, 87–90. doi:10.1016/0012-365X(94)00085-W Google Scholar

[4] [4] Favaron, O., On k-factor-critical graphs. Discuss. Math. Graph Theory 16(1996), no. 1, 41–51. Google Scholar

[5] [5] Katerinis, P. and Woodall, D. R., Binding numbers of graphs and the existence of k-factors. Quart. J. Math. Oxford 38(1987), no. 150, 221–228. doi:10.1093/qmath/38.2.221 Google Scholar

[6] [6] Kano, M., A sufficient condition for a graph to have [a, b]-factors. Graphs Combin. 6(1990), no. 3, 245–251. doi:10.1007/BF01787576 Google Scholar

[7] [7] Li, J., Sufficient conditions for graphs to be (a, b, n)-critical graphs. Math. Appl. (Wuhan) 17(2004), no. 3, 450–455. Google Scholar

[8] [8] Li, J. and Matsuda, H., On (g, f, n)-critical graphs. Ars Combin. 78(2006), 71–82. Google Scholar

[9] [9] Liu, G., (g, f)-factors of graphs. Acta Math. Sci. (Chinese) 14(1994), no. 3, 285–290. Google Scholar

[10] [10] Liu, G. and Wang, J., (a, b, k)-critical graphs. Adv. Math. (China) 27(1998), no. 6, 536–540. Google Scholar

[11] [11] Liu, G. and Yu, Q., k-factors and extendability with prescribed components. Congr. Numer. 139(1999), 77–88. Google Scholar

[12] [12] Matsuda, H., Fan-type results for the existence of [a, b]-factors. Discrete Math. 306(2006), no. 7, 688–693. doi:10.1016/j.disc.2006.01.018 Google Scholar

[13] [13] Woodall, D. R.. The binding number of a graph and its Anderson number. J. Combinatorial Theory Ser. B 15(1973), 225–255. doi:10.1016/0095-8956(73)90038-5 Google Scholar

[14] [14] Zhou, S., Sufficient conditions for (a, b, k)-critical graphs. (Chinese) J. Jilin Univ. Sci. 43(2005), no. 5, 607–609. Google Scholar

[15] [15] Zhou, S.. Some sufficient conditions for graphs to have (g, f)-factors. Bull. Austral. Math. Soc. 75(2007), no. 3, 447–452. doi:10.1017/S0004972700039368 Google Scholar

[16] [16] Zhou, S. and Xue, X., Complete-factors and (g, f)-covered graphs. Australas. J. Combin. 37(2007), 265–269. Google Scholar