Minimal bricks with the maximum number of edges

被引:0
作者
Feng, Xing [1 ,2 ]
Yan, Weigen [1 ]
机构
[1] Jimei Univ, Sch Sci, Xiamen, Peoples R China
[2] Jimei Univ, Sch Sci, Xiamen 361021, Peoples R China
关键词
extremal graph; matching covered graph; minimal brick; perfect matching; PFAFFIAN ORIENTATIONS; PERMANENTS;
D O I
10.1002/jgt.23026
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A 3-connected graph is a brick if, after the removal of any two distinct vertices, the resulting graph has a perfect matching. A brick is minimal if, for every edge e, deleting e results in a graph that is not a brick. Norine and Thomas proved that every minimal brick with 2n vertices, which is distinct from the prism or the wheel on four, six, or eight vertices, has at most 5n - 7 edges. In this paper, we characterize the extremal minimal bricks with 2n vertices that meet this upper bound, and we prove that the number of extremal graphs equals.(n - 1)(2)/4. if n >= 6, 5 if n = 5, 10 if n = 4 and 0 if n = 1, 2, 3, respectively.
引用
收藏
页码:152 / 169
页数:18
相关论文
共 17 条
  • [1] Bondy J.A., 1976, Graph Theory, V290
  • [2] Minimal bricks have many vertices of small degree
    Bruhn, Henning
    Stein, Maya
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 : 261 - 269
  • [3] How to build a brick
    de Carvalho, Marcelo H.
    Lucchesi, Claudio L.
    Murty, U. S. R.
    [J]. DISCRETE MATHEMATICS, 2006, 306 (19-20) : 2383 - 2410
  • [4] BRICK DECOMPOSITIONS AND THE MATCHING RANK OF GRAPHS
    EDMONDS, J
    LOVASZ, L
    PULLEYBLANK, WR
    [J]. COMBINATORICA, 1982, 2 (03) : 247 - 274
  • [5] Generating simple near-bipartite bricks
    Kothari, Nishad
    de Carvalho, Marcelo H.
    [J]. JOURNAL OF GRAPH THEORY, 2020, 95 (04) : 594 - 637
  • [6] Generating near-bipartite bricks
    Kothari, Nishad
    [J]. JOURNAL OF GRAPH THEORY, 2019, 90 (04) : 565 - 590
  • [7] OPERATIONS PRESERVING THE PFAFFIAN PROPERTY OF A GRAPH
    LITTLE, CHC
    RENDL, F
    [J]. JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1991, 50 : 248 - 257
  • [8] MATCHING STRUCTURE AND THE MATCHING LATTICE
    LOVASZ, L
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 43 (02) : 187 - 222
  • [9] Lovasz L., 2009, Matching theory, V367
  • [10] ON TWO UNSOLVED PROBLEMS CONCERNING MATCHING COVERED GRAPHS
    Lucchesi, Claudio L.
    De Carvalho, Marcelo H.
    Kothari, Nishad
    Murty, U. S. R.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 1478 - 1504