How to build a brick
How to build a brick
复制标题
DOI：
10.1016/j.disc.2005.12.032
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
M. H. Carvalho;C. Lucchesi;U. Murty
中科院分区：
文献类型：
--
作者：
M. H. Carvalho;C. Lucchesi;U. Murty
一个图是匹配覆盖的，如果它是连通的，至少有两个顶点，它的每条边都包含在一个完美匹配中。一个3-连通图G称为砖图，如果对G的任意两个顶点u和v，图G-{u，v}有完美匹配.如Lovász所示[匹配结构和匹配晶格，J. Combin.理论系列B 43（1987）187-222]每个匹配覆盖图G可以以基本上唯一的方式分解成称为大括号的砖块和二分图。由该分解产生的砖的数量由B（G）表示。本文的目的是提出一个递归的程序生成砖。我们定义了四个简单的操作，可以用来从给定的砖构建新的砖。我们表明，所有砖块都可以通过这四种操作从三个基本砖块K4、C ¨ 6和彼得森图中生成。为了建立这一点，证明有必要表明，不同于三个基本砖块的每个砖块G都有一个薄边，即边e，使得（i）G-e是匹配覆盖图，B（G-e）=1和（ii）对于G-e的每个障碍B，图G-e-B精确地具有|B|-1个孤立的顶点，每个顶点在G-e中的度为2。对[M. H. de Carvalho，C.L. Lucchesi，苏联Murty，关于Lovász关于砖块的猜想，I，匹配覆盖图的特征，J. Combin。理论系列B 85（2002）94-136; M.H. de Carvalho，C.L. Lucchesi，苏联Murty，关于砖的Lovász猜想，II，有限特征的砖，J. Combin。理论系列B 85（2002）137-180]中，我们在此表明，不同于三种基本砖块的每块砖块都具有薄的边缘。一个匹配覆盖图G的割是分离的，如果通过将割的边收缩为单顶点而从G得到的两个图中的每一个也是匹配覆盖的。一块砖是实心的，如果它没有任何非平凡的分离切口。实心砖有许多有趣的特性，但确定给定砖是否实心的复杂性状态尚不清楚。在这里，通过使用我们的定理薄边的存在性，我们表明，每一个简单的平面固体砖是一个奇数轮。
A graph is matching covered if it connected, has at least two vertices and each of its edges is contained in a perfect matching. A 3-connected graph G is a brick if, for any two vertices u and v of G, the graph G-{u,v} has a perfect matching. As shown by Lovász [Matching structure and the matching lattice, J. Combin. Theory Ser. B 43 (1987) 187–222] every matching covered graph G may be decomposed, in an essentially unique manner, into bricks and bipartite graphs known as braces. The number of bricks resulting from this decomposition is denoted by b(G). The object of this paper is to present a recursive procedure for generating bricks. We define four simple operations that can be used to construct new bricks from given bricks. We show that all bricks may be generated from three basic bricks K4, C¯6and the Petersen graph by means of these four operations. In order to establish this, it turns out to be necessary to show that every brick G distinct from the three basic bricks has a thin edge, that is, an edge e such that (i) G-e is a matching covered graph with b(G-e)=1 and (ii) for each barrier B of G-e, the graph G-e-B has precisely |B|-1 isolated vertices, each of which has degree two in G-e. Improving upon a theorem proved in [M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, On a conjecture of Lovász concerning bricks, I, The characteristic of a matching covered graph, J. Combin. Theory Ser. B 85 (2002) 94–136; M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, On a conjecture of Lovász concerning bricks, II, Bricks of finite characteristic, J. Combin. Theory Ser. B 85 (2002) 137–180] we show here that every brick different from the three basic bricks has an edge that is thin. A cut of a matching covered graph G is separating if each of the two graphs obtained from G by shrinking the shores of the cut to single vertices is also matching covered. A brick is solid if it does not have any nontrivial separating cuts. Solid bricks have many interesting properties, but the complexity status of deciding whether a given brick is solid is not known. Here, by using our theorem on the existence of thin edges, we show that every simple planar solid brick is an odd wheel.