Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-28T03:25:15.341Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  20 November 2018

Sizhong Zhou
Sizhong Zhou*
Affiliation:
School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212003, P.R. China e-mail: zsz [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

05C70graph(g, f)-factor(g, f, n)-critical graphbinding number
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 53 , Issue 2 , 01 June 2010 , pp. 378 - 384
Copyright
Copyright © Canadian Mathematical Society 2010

References

[1] Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications. American Elsevier Publishing, New York, 1976.Google Scholar
[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] 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-WGoogle Scholar
[4] Favaron, O., On k-factor-critical graphs. Discuss. Math. Graph Theory 16(1996), no. 1, 41–51.Google Scholar
[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.221Google Scholar
[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/BF01787576Google Scholar
[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] Li, J. and Matsuda, H., On (g, f, n)-critical graphs. Ars Combin. 78(2006), 71–82.Google Scholar
[9] Liu, G., (g, f)-factors of graphs. Acta Math. Sci. (Chinese) 14(1994), no. 3, 285–290.Google Scholar
[10] Liu, G. and Wang, J., (a, b, k)-critical graphs. Adv. Math. (China) 27(1998), no. 6, 536–540.Google Scholar
[11] Liu, G. and Yu, Q., k-factors and extendability with prescribed components. Congr. Numer. 139(1999), 77–88.Google Scholar
[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.018Google Scholar
[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-5Google Scholar
[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] 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/S0004972700039368Google Scholar
[16] Zhou, S. and Xue, X., Complete-factors and (g, f)-covered graphs. Australas. J. Combin. 37(2007), 265–269.Google Scholar