Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T03:00:53.607Z Has data issue: false hasContentIssue false
  • English
  • Français

NEIGHBOURHOODS OF INDEPENDENT SETS FOR (a,b,k)-CRITICAL GRAPHS

Part of: Graph theory

Published online by Cambridge University Press:  01 April 2008

SIZHONG ZHOU  and
YANG XU
SIZHONG ZHOU*
Affiliation:
School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, People’s Republic of China (email: [email protected])
YANG XU
Affiliation:
Department of Mathematics, Qingdao Agricultural University, Qingdao, Shandong 266109, People’s Republic of China (email: [email protected])
*
✉For correspondence; e-mail: [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 n. Let a, b and k be nonnegative integers such that 1≤a≤b. 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. We provide a sufficient condition for a graph to be (a,b,k)-critical that extends a well-known sufficient condition for the existence of a k-factor.

Keywords

graphminimum degreeneighbourhood[a,b]-factor(a,b,k)-critical graph

MSC classification

Secondary: 05C70: Factorization, matching, partitioning, covering and packing
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 77 , Issue 2 , April 2008 , pp. 277 - 283
Copyright
Copyright © 2008 Australian Mathematical Society

Footnotes

This research was supported by Jiangsu Provincial Educational Department (07KJD110048).

References

[1]Bondy, J. A. and Murty, U. S. R., Graph theory with applications (Macmillan Press, London, 1976).CrossRefGoogle Scholar
[2]Favaron, O., ‘On k-factor-critical graphs’, Discuss. Math. Graph Theory 16(1) (1996), 41–51.CrossRefGoogle Scholar
[3]Li, J., ‘Sufficient conditions for graphs to be (a,b,n)-critical graphs’, Math. Appl. 17(3) (2004), 450–455 (in Chinese).Google Scholar
[4]Li, J., ‘A new degree condition for graph to have [a,b]-factor’, Discrete Math. 290 (2005), 99–103.CrossRefGoogle Scholar
[5]Liu, G. and Wang, J., ‘(a,b,k)-critical graphs’, Adv. Math. 27(6) (1998), 536–540 (in Chinese).Google Scholar
[6]Liu, G. and Yu, Q., ‘k-factors and extendability with prescribed components’, Congr. Numer. 139(1) (1999), 77–88.Google Scholar
[7]Woodall, D. R., ‘k-factors and neighbourhoods of independent sets in graphs’, J. London Math. Soc. 41(2) (1990), 385–392.CrossRefGoogle Scholar
[8]Zhou, S., ‘Some sufficient conditions for graphs to have (g,f)-factors’, Bull. Austral. Math. Soc. 75 (2007), 447–452.CrossRefGoogle Scholar
[9]Zhou, S. and Jiang, J., ‘Notes on the binding numbers for (a,b,k)-critical graphs’, Bull. Austral. Math. Soc. 76 (2007), 307–314.CrossRefGoogle Scholar
[10]Zhou, S. and Zong, M., ‘Some new sufficient conditions for graphs to be (a,b,k)-critical graphs’, Ars Combin. to appear.Google Scholar