A sufficient condition for a graph to be an (a, b, k)-critical graph

Abstract

Let G be a graph, and let a, b, k be integers with 0≤a≤b, k≥0. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a≤d _F (x)≤b for each x∈V(G). 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 article, a sufficient condition is given, which is a neighborhood condition for a graph G to be an (a, b, k)-critical graph.

Keywords:

• graph
• neighborhood
• [a, b]-factor
• (a, b, k)-critical graph

2000 AMS Subject Classification :

• 05C70

Acknowledgements

The author would like to express his gratitude to the referees for their very helpful and detailed comments in improving this article. This research was supported by Jiangsu Provincial Educational Department (07KJD110048) and was sponsored by the Qing Lan Project of Jiangsu Province.