A sufficient condition for a graph to be an \((a, b, k)\)-critical graph. (English) Zbl 1198.05129
Summary: Let \(G\) be a graph, and let \(a, b, k\) be integers with \(0\leq a\leq b, k\geq 0\). An \([a, b]\)-factor of graph \(G\) is defined as a spanning subgraph \(F\) of \(G\) such that \(a\leq d_F(x)\leq b\) for each \(x\in 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.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Alspach, B., Heinrich, K. and Liu, G. 1992.Contemporary Design Theory:A Collection of Surveys, 13–37. New York: Wiley. |
| [2] | DOI: 10.1016/0012-365X(82)90048-6 · Zbl 0525.05048 · doi:10.1016/0012-365X(82)90048-6 |
| [3] | Berge C., Proc. K. Ned. Acad. Wet. Amsterdam (A) 81 pp 165– (1978) |
| [4] | Bondy J. A., Graph Theory with Applications (1976) · Zbl 1226.05083 |
| [5] | DOI: 10.1016/S0012-365X(99)00298-8 · Zbl 0952.05057 · doi:10.1016/S0012-365X(99)00298-8 |
| [6] | Favaron O., Discus. Math. Graph Theory 16 pp 41– (1996) |
| [7] | DOI: 10.1007/BF01787576 · Zbl 0746.05051 · doi:10.1007/BF01787576 |
| [8] | DOI: 10.1016/j.disc.2004.09.010 · Zbl 1059.05085 · doi:10.1016/j.disc.2004.09.010 |
| [9] | Li J., Math. Appl. (China) 17 pp 450– (2004) |
| [10] | Liu G., Adv. Math. (China) 27 pp 536– (1998) |
| [11] | Liu G., Congr. Numer. 139 pp 77– (1999) |
| [12] | DOI: 10.4134/BKMS.2008.45.1.053 · Zbl 1143.05070 · doi:10.4134/BKMS.2008.45.1.053 |
| [13] | DOI: 10.1017/S0004972700039368 · Zbl 1144.05055 · doi:10.1017/S0004972700039368 |
| [14] | Zhou S., J. Jilin Univ. Sci. (China) 43 pp 607– (2005) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
