UNI-MB - logo
UMNIK - logo
 
E-viri
Recenzirano Odprti dostop
  • Generating bricks
    Norine, Serguei; Thomas, Robin

    Journal of combinatorial theory. Series B, 09/2007, Letnik: 97, Številka: 5
    Journal Article

    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.