Generalization of matching extensions in graphs (II) Original Research Article

Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311–320.] introduced (n,k,d)(n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,kn,k and d be non-negative integers such that n+2k+d⩽|V(G)|-2n+2k+d⩽|V(G)|-2 and |V(G)|-n-d|V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)(n,k,d)-graph. Liu and Yuʹs Papeeʹs paper, the recursive relations for distinct parameters n,kn,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)(n,k,d)-graphs in the general case d⩾0d⩾0.