Title of article
Minimum degree of minimal defect -extendable bipartite graphs
Author/Authors
Wen، نويسنده , , Xuelian and Yang، نويسنده , , Zihui، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
10
From page
6255
To page
6264
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
Serial Year
2009
Journal title
Discrete Mathematics
Record number
1599173
Link To Document