How to build a brick. (English) Zbl 1106.05075
A graph is said to be matching covered if it is connected, has at least two vertices and each of its edges is contained in a perfect matching. A 3-connected graph \(G\) is called a brick if, for any two vertices \(u\) and \(v\) of \(G\), the graph obtained from \(G\) after removing the vertices \(u\) and \(v\) has a perfect matching. The purpose of this paper is to present a recursive procedure for generating bricks. It is shown that all bricks may be generated from three basic bricks by means of four simple operations, so that every brick different from the three basic bricks has an edge called thin edge, and that every simple planar solid brick is an odd wheel, where a brick is solid if it does not have any nontrivial separating cuts.
Reviewer: Wai-Kai Chen (Fremont)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., On a conjecture of Lovász concerning bricks, I, The characteristic of a matching covered graph, J. Combin. Theory Ser. B, 85, 94-136 (2002) · Zbl 1024.05069 |
| [2] | de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., On a conjecture of Lovász concerning bricks, II, Bricks of finite characteristic, J. Combin. Theory Ser. B, 85, 137-180 (2002) · Zbl 1024.05070 |
| [3] | de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., Optimal ear decompositions of matching covered graphs, J. Combin. Theory Ser. B, 85, 59-93 (2002) · Zbl 1024.05071 |
| [4] | de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., The perfect matching polytope and solid bricks, J. Combin. Theory Ser. B, 92, 319-324 (2004) · Zbl 1055.05128 |
| [5] | de Carvalho, M. H.; Lucchesi, C. L.; Murty, U. S.R., Graphs with independent perfect matchings, J. Graph Theory, 48, 19-50 (2005) · Zbl 1055.05127 |
| [6] | Edmonds, J.; Lovász, L.; Pulleyblank, W. R., Brick decomposition and the matching rank of graphs, Combinatorica, 2, 247-274 (1982) · Zbl 0521.05035 |
| [7] | Little, C. H.C.; Rendl, F., Operations preserving the Pfaffian property of a graph, J. Austral. Math. Soc. Ser. A, 50, 248-275 (1991) · Zbl 0749.05050 |
| [8] | Lovász, L., Matching structure and the matching lattice, J. Combin. Theory Ser. B, 43, 187-222 (1987) · Zbl 0659.05081 |
| [9] | Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, vol. 29 (1986), Elsevier Science: Elsevier Science Amsterdam · Zbl 0618.05001 |
| [10] | C.L. Lucchesi, On the integer cone of a solid brick, manuscript, 2001.; C.L. Lucchesi, On the integer cone of a solid brick, manuscript, 2001. |
| [11] | McCuaig, W., Brace generation, J. Graph Theory, 38, 124-169 (2001) · Zbl 0991.05086 |
| [12] | Seymour, P. D., On multicolourings of cubic graphs and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3), 38, 423-460 (1979) · Zbl 0411.05037 |
| [13] | Szigeti, Z., Perfect matchings versus odd cuts, Combinatorica, 22, 575-590 (2002) · Zbl 1026.05090 |
| [14] | Thomassen, C., Plane representations of graphs, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press: Academic Press New York), 46-69 · Zbl 0554.05021 |
| [15] | Tutte, W. T., Connectivity in Graphs, Mathematical Expositions, vol. 5 (1961), University of Toronto Press: University of Toronto Press Toronto · Zbl 0104.17704 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
