How to build a brick
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.
- Brace generation
- Brick decompositions and the matching rank of graphs
- Graphs with independent perfect matchings
- scientific article; zbMATH DE number 3882450 (Why is no real title available?)
- scientific article; zbMATH DE number 3170046 (Why is no real title available?)
- scientific article; zbMATH DE number 13859 (Why is no real title available?)
- Matching structure and the matching lattice
- Matching theory
- On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
- On a conjecture of Lovász concerning bricks. II: Bricks of finite characteristic
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
- Optimal ear decompositions of matching covered graphs and bases for the matching lattice
- Perfect matchings versus odd cuts
- The perfect matching polytope and solid bricks
- On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
- A generalization of Little's theorem on Pfaffian orientations
- Relations between global forcing number and maximum anti-forcing number of a graph
- On essentially 4-edge-connected cubic bricks
- \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
- Minimal bricks have many vertices of small degree
- Minimal bricks
- Generating bricks
- Brace generation
- \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
- On two unsolved problems concerning matching covered graphs
- Disjoint odd cycles in cubic solid bricks
- Matching extension in prism graphs
- Birkhoff-von Neumann graphs that are PM-compact
- Cubic graphs with 3-edge coloring of graphs
- The cubic vertices of minimal bricks
- On extremal nonsolid bricks
- Minimally k-factor-critical graphs for some large k
- A characterization of nonfeasible sets in matching covered graphs
- Generating simple near‐bipartite bricks
- The cubic vertices of solid minimal bricks
- Minimum degree of minimal (n-10)-factor-critical graphs
- Colouring non-even digraphs
- On a Norine-Thomas conjecture concerning minimal bricks
- Planar cycle-extendable graphs
- Wheel-like bricks and minimal matching covered graphs
- Thin edges in claw-free bricks
- Claw-free solid bricks
- K₄-free planar minimal bricks with the maximum number of edges
- Minimal bricks with the maximum number of edges
- Cubic vertices of minimal matching covered graphs
- Lattice structure and efficient basis construction for strongly connected orientations
- b-invariant edges in near-bipartite bricks
- Nice pairs of disjoint pentagons in fullerene graphs
- Nice pairs of odd cycles in fullerene graphs
- Thin edges in braces
- Brick partitions of graphs
This page was built for publication: How to build a brick
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433703)
