Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648951 | Discrete Mathematics | 2009 | 10 Pages |
A near perfect matching is a matching saturating all but one vertex in a graph. If GG is a connected graph and any nn independent edges in GG are contained in a near perfect matching, then GG is said to be defect nn-extendable. If for any edge ee in a defect nn-extendable graph GG, G−eG−e is not defect nn-extendable, then GG is minimal defect nn-extendable. The minimum degree and the connectivity of a graph GG are denoted by δ(G)δ(G) and κ(G)κ(G) respectively. In this paper, we study the minimum degree of minimal defect nn-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph GG has δ(G)=1δ(G)=1. Consider a minimal defect nn-extendable bipartite graph GG with n≥2n≥2, we show that if κ(G)=1κ(G)=1, then δ(G)≤n+1δ(G)≤n+1 and if κ(G)≥2κ(G)≥2, then 2≤δ(G)=κ(G)≤n+12≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.