Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T00:36:03.943Z Has data issue: false hasContentIssue false
  • English
  • Français

Notes on the binding numbers for (a, b, k)-critical graphs

Published online by Cambridge University Press:  17 April 2009

Sizhong Zhou  and
Jiashang Jiang
Sizhong Zhou
Affiliation:
School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003People's Republic of China e-mail address: [email protected]
Jiashang Jiang
Affiliation:
School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003People's Republic of China e-mail address: [email protected]
Rights & Permissions [Opens in a new window]

Extract

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 n, and let a, b, k be nonnegative integers with 1 ≤ a < b. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a ≤ dF(x) ≤ b for each x ϵ V (F). Then a graph G is called an (a, b, k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a, b]-factor. In this paper, it is proved that G is an (a, b, k)-critical graph if the binding number and

Furthermore, it is showed that the result in this paper is best possible in some sense.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 76 , Issue 2 , October 2007 , pp. 307 - 314
Copyright
Copyright © Australian Mathematical Society 2007

References

[1]Bondy, J.A. and Murty, U.S.R., Graph theory with applications (The Macmillan Press, London, 1976).CrossRefGoogle Scholar
[2]Chen, C., ‘Binding number and minimum degree for [a, b]-factor’, J. Systems Sci. Math. Sci. 6 (1993), 179–185.Google Scholar
[3]Kano, M., ‘A sufficient condition for a graph to have [a, b]-factors’, Graphs Combin. 6 (1990), 245–251.CrossRefGoogle Scholar
[4]Katerinis, P. and Woodall, D.R., ‘Binding numbers of graphs and the existence of k-factors’, Quart. J. Math. Oxford 38 (1987), 221–228.CrossRefGoogle Scholar
[5]Li, J., ‘Sufficient conditions for graphs to be (a, b, n)-critical graphs’, Mathematica Applicata (Wuhan) 17 (2004), 450–455.Google Scholar
[6]Li, Y. and Cai, M., ‘A degree condition for a graph to have [a, b]-factors’, J. Graph Theory 27 (1998), 1–6.3.0.CO;2-U>CrossRefGoogle Scholar
[7]Liu, G., ‘(g < f)-factors of graphs’, Acta Math. Sci. (Chinese) 14 (1994), 285–290.Google Scholar
[8]Liu, G. and Wang, J., ‘(a, b, k)-critical graphs’, Adv. Math. (China) 27 (1998), 536–540.Google Scholar
[9]Matsuda, H., ‘Fan-type results for the existence of [a, b]-factors’, Discrete Math. 306 (2006), 688–693.CrossRefGoogle Scholar
[10]Zhou, S., ‘Some sufficient conditions for graphs to have (g, f)-factors’, Bull. Austral. Math. Soc. 75 (2007), 447–452.CrossRefGoogle Scholar
[11]Zhou, S. and Xue, X., ‘(g, f)-factors of graphs with prescribed properties’, J. Systems Sci. Math. Sci. (Chinese) (to appear).Google Scholar
[12]Zhou, S. and Xue, X., ‘Complete-factors and (g, f)-covered graphs’, Australas. J. Combin. 37 (2007), 265–269.Google Scholar
[13]Zhou, S., ‘Sufficient conditions for (a, b, k)-critical graphs’, J. Jilin Univ. Sci. 43 (2005), 607–609.Google Scholar