Generalization of matching extensions in graphs (III)

Proposing them as a general framework, Liu and Yu (2001) [6] introduced (n,k,d)(n,k,d)-graphs to unify the concepts of deficiency of matchings, nn-factor-criticality and kk-extendability. Let GG be a graph and let n,kn,k and dd be non-negative integers such that n+2k+d+2⩽|V(G)|n+2k+d+2⩽|V(G)| and |V(G)|−n−d|V(G)|−n−d is even. If on deleting any nn vertices from GG the remaining subgraph HH of GG contains a kk-matching and each kk-matching can be extended to a defect-dd matching in HH, then GG is called an (n,k,d)(n,k,d)-graph  . In this paper, we obtain more properties of (n,k,d)(n,k,d)-graphs, in particular the recursive relations of (n,k,d)(n,k,d)-graphs for distinct parameters n,kn,k and dd. Moreover, we provide a characterization for maximal non-(n,k,d)(n,k,d)-graphs.