A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k  -factor-critical but G+eG+e is k  -factor-critical for every missing edge e∉E(G)e∉E(G). A connected graph G   with a perfect matching on 2n2n vertices is k  -extendable, for 1⩽k⩽n-11⩽k⩽n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k  -extendable but G+eG+e is k  -extendable for every missing edge e∉E(G)e∉E(G) . A connected bipartite graph G   with a bipartitioning set (X,Y)(X,Y) such that |X|=|Y|=n|X|=|Y|=n is maximal non-k-extendable bipartite if G is not k  -extendable but G+xyG+xy is k  -extendable for any edge xy∉E(G)xy∉E(G) with x∈Xx∈X and y∈Yy∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.