Minimal bricks

被引：13

作者：

Norine, Serguei ^{[1
]}

Thomas, Robin ^{[1
]}

机构：

[1] Georgia Tech, Sch Math, Atlanta, GA 30332 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2006年 / 96卷 / 04期

基金：

美国国家科学基金会;

关键词：

graph; perfect matching; brick; minimal brick;

D O I：

10.1016/j.jctb.2005.10.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge e the deletion of e results in a graph that is not a brick. We prove a generation theorem for minimal bricks and two corollaries: (1) for it >= 5, every minimal brick on 2n vertices has at most 5n-7 edges. and (2) every minimal brick has at least three vertices of degree three. (C) 2006 Robin Thomas. Published by Elsevier Inc. All rights reserved.

引用

页码：505 / 513

页数：9

共 7 条

[1]

DECARVALHO MH, IN PRESS DISCRETE MA

[2] BRICK DECOMPOSITIONS AND THE MATCHING RANK OF GRAPHS [J].