MM-alternating paths and the construction of defect nn-extendable bipartite graphs with different connectivities

A near perfect matching is a matching covering all but one vertex in a graph. Let GG be a connected graph and n≤(|V(G)|−2)/2n≤(|V(G)|−2)/2 be a positive integer. If any nn independent edges in GG are contained in a near perfect matching, then GG is said to be defectnn-extendable. In this paper, we first characterize defect nn-extendable bipartite graph GG with n=1n=1 or κ(G)≥2κ(G)≥2 respectively using MM-alternating paths. Furthermore, we present a construction characterization of defect nn-extendable bipartite graph GG with n≥2n≥2 and κ(G)=1κ(G)=1. It is also shown that these characterizations can be transformed to polynomial time algorithms to determine if a given bipartite graph is defect nn-extendable.