Generalization of matching extensions in graphs (II)

Abstract

Proposed as a general framework, Liu and Yu(Discrete Math. 231 (2001) 311-320) introduced $(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,k$ and $d$ be non-negative integers such that $n+2k+d\le |V(G)|-2$ and $|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)$-graph. In \cite{Liu}, the recursive relations for distinct parameters $n,k$ and $d$ were presented and the impact of adding or deleting an edge also was discussed for the case $d=0$. In this paper, we continue the study begun in \cite{Liu} and obtain new recursive results for $(n,k,d)$-graphs in the general case $d\ge 0$.

12 pages