Generating bricks
Generating bricks
复制标题
DOI：
10.1016/j.jctb.2007.01.002
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Sergey Norin;R. Thomas
中科院分区：
文献类型：
--
作者：
Sergey Norin;R. Thomas
砖是一个3连通图，使得从它删除任何两个不同的顶点得到的图具有完美匹配。砖的重要性源于这样一个事实，即它们是Kotzig、Lovász和Plummer的匹配分解过程的构建块。我们证明了一个“分裂定理”的砖。更确切地说，我们表明，如果一个砖H是一个“匹配的小”的砖G，然后，除了少数描述良好的例外，一个图同构H可以从G通过重复应用某种操作，以这样一种方式，所有的中间图是砖，没有平行的边缘。其操作如下：首先删除一条边，对于每一个度为2的顶点，其结果是与之关联的两条边都收缩，这加强了de Carvalho，Lucchesi和Murty最近的一个结果。
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of the matching decomposition procedure of Kotzig, and Lovász and Plummer. We prove a “splitter theorem” for bricks. More precisely, we show that if a brick H is a “matching minor” of a brick G, then, except for a few well-described exceptions, a graph isomorphic to H can be obtained from G by repeatedly applying a certain operation in such a way that all the intermediate graphs are bricks and have no parallel edges. The operation is as follows: first delete an edge, and for every vertex of degree two that results contract both edges incident with it. This strengthens a recent result of de Carvalho, Lucchesi and Murty.