Minimally \(k\)-factor-critical graphs for some large \(k\). (English) Zbl 1518.05153
Summary: A graph \(G\) of order \(n\) is said to be \(k\)-factor-critical for integers \(1\leq k < n\), if the removal of any \(k\) vertices results in a graph with a perfect matching. 1- and 2-factor-critical graphs are the well-known factor-critical and bicritical graphs, respectively. A \(k\)-factor-critical graph \(G\) is called minimal if for any edge \(e\in E(G), G-e\) is not \(k\)-factor-critical. O. Favaron and M. Shi [Australas. J. Comb. 17, 89–97 (1998; Zbl 0907.05042)] conjectured that every minimally \(k\)-factor-critical graph of order \(n\) has the minimum degree \(k+1\) and confirmed it for \(k=1, n-2, n-4\) and \(n-6\). In this paper, we use a simple method to reprove the above results. As a main result, the further use of this method enables us to prove the conjecture to be true for \(k=n-8\). We also obtain that every minimally \((n-6)\)-factor-critical graph of order \(n\) has at most \(n-\Delta (G)\) vertices with the maximum degree \(\Delta (G)\) for \(\Delta (G)\geq n-4\).
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 05C07 | Vertex degrees |
Citations:
Zbl 0907.05042References:
| [1] | Bruhn, H.; Stein, M., Minimal bricks have many vertices of small degree, Eur. J. Comb., 36, 261-269 (2014) · Zbl 1284.05208 · doi:10.1016/j.ejc.2013.06.045 |
| [2] | de Carvalho, MH; Lucchesi, CL; Murty, USR, How to build a brick, Discrete Math., 306, 2386-2410 (2006) · Zbl 1106.05075 · doi:10.1016/j.disc.2005.12.032 |
| [3] | Favaron, O., On \(k\)-factor-critical graphs, Discuss. Math. Graph Theory, 16, 41-51 (1996) · Zbl 0865.05061 · doi:10.7151/dmgt.1022 |
| [4] | Favaron, O.; Shi, M., Minimally \(k\)-factor-critical graphs, Australas. J. Comb., 17, 89-97 (1998) · Zbl 0907.05042 |
| [5] | Favaron, O.; Flandrin, E.; Ryjáček, Z., Factor-criticality and matching extension in DCT-graphs, Discuss. Math. Graph Theory, 17, 271-278 (1997) · Zbl 0907.05040 · doi:10.7151/dmgt.1054 |
| [6] | Gallai, T., Neuer Beweis eines Tutte’schen Satzes, Magyar Tud, Akad. Mat. Kutató Int. Közl., 8, 135-139 (1963) · Zbl 0129.39802 |
| [7] | Lovász, L., On the structure of factorizable graphs, Acta Math. Acad. Sci. Hungar., 23, 179-195 (1972) · Zbl 0247.05156 · doi:10.1007/BF01889914 |
| [8] | Lou, D., On the structure of minimally \(n\)-extendable bipartite graphs, Discrete Math., 202, 173-181 (1999) · Zbl 0931.05069 · doi:10.1016/S0012-365X(98)00291-X |
| [9] | Lou, D., On matchability of graphs, Australas. J. Comb., 21, 201-210 (2000) · Zbl 0947.05062 |
| [10] | Lou, D., Some conditions for \(n\)-extendable graphs, Australas. J. Comb., 9, 123-136 (1994) · Zbl 0805.05066 |
| [11] | Lovász, L., Plummer, M. D.: Matching theory. Ann. Discrete Math. 29 (1986) · Zbl 0618.05001 |
| [12] | Lou, D.; Yu, Q., Connectivity of \(k\)-extendable graphs with large \(k\), Discrete Appl. Math., 136, 55-61 (2004) · Zbl 1036.05041 · doi:10.1016/S0166-218X(03)00198-7 |
| [13] | Lou, D.; Yu, Q., Sufficient conditions for \(n\)-matchable graphs, Australas. J. Comb., 29, 127-133 (2004) · Zbl 1061.05074 |
| [14] | Lin, F.; Zhang, L.; Lu, F., The cubic vertices of minimal bricks, J. Graph Theory, 76, 20-33 (2014) · Zbl 1294.05097 · doi:10.1002/jgt.21747 |
| [15] | Nishimura, T., A closure concept in factor-critical graphs, Discrete Math., 259, 319-324 (2002) · Zbl 1014.05052 · doi:10.1016/S0012-365X(02)00303-5 |
| [16] | Norine, S.; Thomas, R., Minimal bricks, J. Comb. Theory Ser. B, 96, 505-513 (2006) · Zbl 1092.05056 · doi:10.1016/j.jctb.2005.10.005 |
| [17] | Plummer, MD; Bodendiek, R., Degree sums, neighborhood unions and matching extension in graphs, Contemporary Methods in Graph Theory (B), 489-502 (1990), Mannheim: I. Wissenschaftsverlag, Mannheim · Zbl 0745.05041 |
| [18] | Plummer, MD; Saito, A., Closure and factor-critical graphs, Discrete Math., 215, 171-179 (2000) · Zbl 0951.05084 · doi:10.1016/S0012-365X(99)00234-4 |
| [19] | Tutte, WT, The factorization of linear graphs, J. Lond. Math. Soc., 22, 107-111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107 |
| [20] | Yu, Q., Characterizations of various matching extensions in graphs, Australas. J. Comb., 7, 55-64 (1993) · Zbl 0783.05085 |
| [21] | Yu, Q.; Liu, G., Graph Factors and Matching Extensions (2009), Beijing: Higher Education Press, Beijing · Zbl 1232.05001 · doi:10.1007/978-3-540-93952-8 |
| [22] | Zhang, Z.; Wang, T.; Lou, D., Equivalence between extendibility and factor-criticality, Ars Comb., 85, 279-285 (2007) · Zbl 1224.05430 |
| [23] | Zhai, S.; Wei, E.; Zhang, F., The characterization of \(p\)-factor-critical graphs, Acta Math. Appl. Sin. (English Ser.), 38, 154-158 (2022) · Zbl 1484.05170 · doi:10.1007/s10255-022-1064-x |
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.
