Title of article :
Minimum degree of minimal defect -extendable bipartite graphs
Author/Authors :
Wen، نويسنده , , Xuelian and Yang، نويسنده , , Zihui، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n -extendable. If for any edge e in a defect n -extendable graph G , G − e is not defect n -extendable, then G is minimal defect n -extendable. The minimum degree and the connectivity of a graph G are denoted by δ ( G ) and κ ( G ) respectively. In this paper, we study the minimum degree of minimal defect n -extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ ( G ) = 1 . Consider a minimal defect n -extendable bipartite graph G with n ≥ 2 , we show that if κ ( G ) = 1 , then δ ( G ) ≤ n + 1 and if κ ( G ) ≥ 2 , then 2 ≤ δ ( 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.
Keywords :
Near perfect matching , Minimal defect n -extendable , Defect n -extendable
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics