Minimal bricks have many vertices of small degree

被引：5
作者：
Bruhn, Henning [1 ]
Stein, Maya [2 ]
机构：
[1] Univ Paris 06, F-75252 Paris 05, France
[2] Univ Chile, Ctr Modelamiento Matemat, Santiago 2120, Chile
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2014年 / 36卷
关键词：
D O I：
10.1016/j.ejc.2013.06.045
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We prove that every minimal brick on n vertices has at least n/9 vertices of degree at most 4. (C) 2013 Published by Elsevier Ltd
引用
收藏
页码：261 / 269
页数：9
相关论文
共 8 条
  • [1] [Anonymous], 2003, COMBINATORIAL OPTIMI
  • [2] 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
  • [3] BRICK DECOMPOSITIONS AND THE MATCHING RANK OF GRAPHS
    EDMONDS, J
    LOVASZ, L
    PULLEYBLANK, WR
    [J]. COMBINATORICA, 1982, 2 (03) : 247 - 274
  • [4] 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
  • [5] MATCHING STRUCTURE AND THE MATCHING LATTICE
    LOVASZ, L
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 43 (02) : 187 - 222
  • [6] Lovasz L., 1986, MATCHING THEORY
  • [7] Generating bricks
    Norine, Serguei
    Thomas, Robin
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) : 769 - 817
  • [8] Minimal bricks
    Norine, Serguei
    Thomas, Robin
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 505 - 513
1