Maximum matchings in regular graphs of high girth

被引:0
作者
Flaxman, Abraham D. [1 ]
Hoory, Shlomo
机构
[1] Microsoft Res, Redmond, WA 98052 USA
[2] IBM Res Lab, Haifa, Israel
关键词
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G = (V, E) be any d-regular graph with girth g on n vertices, for d >= 3. This note shows that G has a maximum matching which includes all but an exponentially small fraction of the vertices, O((d - 1)(-g/2)). Specifically, in a maximum matching of G, the number of unmatched vertices is at most n/n(o) (d, g), where no (d, g) is the number of vertices in a ball of radius [(g - 1)/2] around a vertex, for odd values of g, and around an edge, for even values of g. This result is tight if n < 2n(o) (d, g).
引用
收藏
页数:4
相关论文
共 9 条
[1]  
ALON A, 2002, J COMBINATORIAL TH B, V84, P340
[2]   The Moore bound for irregular graphs [J].
Alon, N ;
Hoory, S ;
Linial, N .
GRAPHS AND COMBINATORICS, 2002, 18 (01) :53-57
[3]   Matching, matroids, and extensions [J].
Cunningham, WH .
MATHEMATICAL PROGRAMMING, 2002, 91 (03) :515-542
[4]  
EDMONDS J, J RES NBS B, V69, P125
[5]  
IGGS N, 1993, ALGEBRAIC GRAPH THEO
[6]   A NEW SERIES OF DENSE GRAPHS OF HIGH GIRTH [J].
LAZEBNIK, F ;
USTIMENKO, VA ;
WOLDAR, AJ .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 32 (01) :73-79
[7]   RAMANUJAN GRAPHS [J].
LUBOTZKY, A ;
PHILLIPS, R ;
SARNAK, P .
COMBINATORICA, 1988, 8 (03) :261-277
[8]  
Margulis G. A., 1988, Problems of Information Transmission, V24, P39
[9]   CAGES - A SURVEY [J].
WONG, PK .
JOURNAL OF GRAPH THEORY, 1982, 6 (01) :1-22