M-alternating paths and the construction of defect n-extendable bipartite graphs with different connectivities

AbstractA near perfect matching is a matching covering all but one vertex in a graph. Let G be a connected graph and n≤(|V(G)|−2)/2 be a positive integer. If any n independent edges in G are contained in a near perfect matching, then G is said to be defectn-extendable. In this paper, we first characterize defect n-extendable bipartite graph G with n=1 or κ(G)≥2 respectively using M-alternating paths. Furthermore, we present a construction characterization of defect n-extendable bipartite graph G with n≥2 and κ(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 n-extendable