Matchings in graphs of odd regularity and girth

被引：5
作者：
Costa, Vitor [1 ]
Dantas, Simone [1 ]
Rautenbach, Dieter [2 ]
机构：
[1] Univ Fed Fluminense, Inst Matemat & Estat, Niteroi, RJ, Brazil
[2] Univ Ulm, Inst Optimizat & Operat Res, D-89069 Ulm, Germany
来源：
DISCRETE MATHEMATICS | 2013年 / 313卷 / 24期
关键词：
Matching; Regular graph; Odd girth; EIGENVALUES; BOUNDS;
D O I：
10.1016/j.disc.2013.08.030
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We establish lower bounds on the matching number of graphs of given odd regularity d and odd girth g, which are sharp for many values of d and g. For d = g = 5, we characterize all extremal graphs. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：2895 / 2902
页数：8
相关论文
共 12 条
  • [1] Tight bounds on maximal and maximum matchings
    Biedl, T
    Dernaine, ED
    Duncan, CA
    Fleischer, R
    Kobourov, SG
    [J]. DISCRETE MATHEMATICS, 2004, 285 (1-3) : 7 - 15
  • [2] Matchings in regular graphs from eigenvalues
    Cioaba, Sebastian M.
    Gregory, David A.
    Haemers, Willem H.
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (02) : 287 - 297
  • [3] PATHS TREES AND FLOWERS
    EDMONDS, J
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03): : 449 - &
  • [4] Flaxman A. D., 2007, ELECTRON J COMB, V14, p#N1
  • [5] Tight lower bounds on the size of a maximum matching in a regular graph
    Henning, Michael A.
    Yeo, Anders
    [J]. GRAPHS AND COMBINATORICS, 2007, 23 (06) : 647 - 657
  • [6] Independent sets and matchings in subcubic graphs
    Henning, Michael A.
    Loewenstein, Christian
    Rautenbach, Dieter
    [J]. DISCRETE MATHEMATICS, 2012, 312 (11) : 1900 - 1910
  • [7] Petersen J., 1891, ACTA MATH, V15, P193, DOI [DOI 10.1007/BF02392606, 10.1007/BF02392606]
  • [8] Plummer MichaelD., 1986, Matching theory, V29
  • [9] EDGE-CONNECTIVITY, EIGENVALUES, AND MATCHINGS IN REGULAR GRAPHS
    Suil, O.
    Cioaba, Sebastian M.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1470 - 1481
  • [10] Balloons, Cut-Edges, Matchings, and Total Domination in Regular Graphs of Odd Degree
    Suil, O.
    West, Douglas B.
    [J]. JOURNAL OF GRAPH THEORY, 2010, 64 (02) : 116 - 131
12