Abstract
A graph G is said to be p-factor-critical if G−u1−u2−ï−up has a perfect matching for any u1, u2, ⋯ up ∈ V(G). The concept of p-factor-critical is a generalization of the concepts of factor-critical and bicritical for p = 1 and p = 2, respectively. Heping Zhang and Fuji Zhang[Construction for bicritical graphs and k-extendable bipartite graphs, Discrete Math., 306(2006) 1415–1423] gave a concise structure characterization of bicritical graphs. In this paper, we present the characterizations of p-factor-critical graphs and minimal p-factor-critical graphs for p ≥ 2. As an application, we also obtain a class of graphs which are minimal p-factor-critical for p ≥ 1.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldred, R.E.L., Holton, D.A., Lou, D., Zhong, N. Characterizing 2p-critical graphs and k-extedable graphs. Discrete Math., 287: 135–139 (2004)
Berge, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973
Bondy, J.A., Murty, U.S.R. Graph Theory. Springer, Verlag, New York, 2008
Favaron, O. On k-factor-critical graphs, Discuss. Math. Graph Theory, 16: 41–51 (1996)
Favaron, O. Extendability and factor-criticality. Discrete Math., 213: 115–122 (2000)
Favaron, O., Flandrin, E., Ryjáček, Z. Factor-criticality and matching extension in DCT-graphs. Discuss. Math. Graph Theory, 17: 271–278 (1997)
Favaron, O., Shi, M. k-factor-critical graphs and induced subgraphs. Congr. Numer., 122: 59–66 (1996)
Favaron, O., Shi, M. Minimally k-factor-critical graphs. Australas. J. Combin., 17: 89–97 (1998)
Lawler, E.L. Covering problems: duality relations and a new method of solutions. SIAM J. Appl. Math., 14: 1115–1132 (1966)
Lovasz, L., Plummer, M.D. Matching Theory. Ann. Discrete Math., Vol.29, North-Holland, Amsterdam, 1986
Maghout, K. Sur la determination des nombres de stabiliteet du nombre chromatique d’un graphe. C.R. Acad. Sci. Paris, 248: 3522–3523 (1959)
Wen, X., Lou, D. Characterizeing defect p-extendable graphs and (2p + 1)-critical graphs. Discrete Math., 308: 5064–5069 (2008)
Zhang, F., Zhang, H. Construction for bicritical graphs and k-extendable bipartite graphs. Discrete Math., 306: 1415–1423 (2006)
Funding
Supported by the National Natural Science Foundation of China (No. 11401576).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhai, Sh., Wei, El. & Zhang, Fj. The Characterization of p-factor-critical Graphs. Acta Math. Appl. Sin. Engl. Ser. 38, 154–158 (2022). https://doi.org/10.1007/s10255-022-1064-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-022-1064-x