• 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