Generalization of matching extensions in graphs (II)

Abstract: Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311–320.] introduced -graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let and d be non-negative integers such that and 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 -graph. Liu and Yu''s Papee''s paper, the recursive relations for distinct parameters and d were presented and the impact of adding or deleting an edge also was discussed for the case . In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for -graphs in the general case . [Copyright &y& Elsevier]