Minimal bricks with the maximum number of edges

被引:1
作者
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]  
[Anonymous], 2009, Matching theory
[2]  
Bondy JA, 1976, Graph Theory
[3]   Minimal bricks have many vertices of small degree [J].
Bruhn, Henning ;
Stein, Maya .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 :261-269
[4]   How to build a brick [J].
de Carvalho, Marcelo H. ;
Lucchesi, Claudio L. ;
Murty, U. S. R. .
DISCRETE MATHEMATICS, 2006, 306 (19-20) :2383-2410
[5]   BRICK DECOMPOSITIONS AND THE MATCHING RANK OF GRAPHS [J].
EDMONDS, J ;
LOVASZ, L ;
PULLEYBLANK, WR .
COMBINATORICA, 1982, 2 (03) :247-274
[6]   Generating simple near-bipartite bricks [J].
Kothari, Nishad ;
de Carvalho, Marcelo H. .
JOURNAL OF GRAPH THEORY, 2020, 95 (04) :594-637
[7]   Generating near-bipartite bricks [J].
Kothari, Nishad .
JOURNAL OF GRAPH THEORY, 2019, 90 (04) :565-590
[8]   OPERATIONS PRESERVING THE PFAFFIAN PROPERTY OF A GRAPH [J].
LITTLE, CHC ;
RENDL, F .
JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1991, 50 :248-257
[9]   MATCHING STRUCTURE AND THE MATCHING LATTICE [J].
LOVASZ, L .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 43 (02) :187-222
[10]   ON TWO UNSOLVED PROBLEMS CONCERNING MATCHING COVERED GRAPHS [J].
Lucchesi, Claudio L. ;
De Carvalho, Marcelo H. ;
Kothari, Nishad ;
Murty, U. S. R. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) :1478-1504