On essentially 4-edge-connected cubic bricks

DOI10.37236/8594MaRDI QIDQ2290348zbMATH OpenOpenAlexFDO

Authors Nishad Kothari, Marcelo H. de Carvalho, Cláudio L. Lucchesi, C. H. C. Little

Publication date 27 January 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1803.08713, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p22

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: Lov'asz (1987) proved that every matching covered graph $G$ may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let $b(G)$ denote the number of bricks. An edge $e$ is removable if $G-e$ is also matching covered; furthermore, $e$ is $b$-invariant if $b(G-e)=1$, and $e$ is quasi-$b$-invariant if $b(G-e)=2$. (Each edge of the Petersen graph is quasi-$b$-invariant.) A brick $G$ is near-bipartite if it has a pair of edges $e,f$ so that $G-e-f$ is matching covered and bipartite; such a pair $e,f$ is a removable doubleton. (Each of $K_4$ and the triangular prism $overline{C}_6$ has three removable doubletons.) Carvalho, Lucchesi and Murty (2002) proved a conjecture of Lov'asz which states that every brick, distinct from $K_4$, $overline{C}_6$ and the Petersen graph, has a $b$-invariant edge. A cubic graph is essentially $4$-edge-connected if it is $2$-edge-connected and if its only $3$-cuts are the trivial ones; it is well-known that each such graph is either a brick or a brace; we provide a graph-theoretical proof of this fact. We prove that if $G$ is any essentially $4$-edge-connected cubic brick then its edge-set may be partitioned into three (possibly empty) sets: (i) edges that participate in a removable doubleton, (ii) $b$-invariant edges, and (iii) quasi-$b$-invariant edges; our Main Theorem states that if $G$ has two adjacent quasi-$b$-invariant edges, say $e_1$ and $e_2$, then either $G$ is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of $G$ (distinct from $e_1$ and $e_2$) is $b$-invariant. As a corollary, we deduce that each essentially $4$-edge-connected cubic non-near-bipartite brick $G$, distinct from the Petersen graph, has at least $|V(G)|$ $b$-invariant edges.

Review text

Summary: \textit{L. Lovász} [J. Comb. Theory, Ser. B 43, 187--222 (1987; Zbl 0659.05081)] proved that every matching covered graph \(G\) may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let \(b(G)\) denote the number of bricks. An edge \(e\) is removable if \(G-e\) is also matching covered; furthermore, \(e\) is \(b\)-invariant if \(b(G-e)=1\), and \(e\) is quasi-\(b\)-invariant if \(b(G-e)=2\). (Each edge of the Petersen graph is quasi-\(b\)-invariant.) A brick \(G\) is near-bipartite if it has a pair of edges \(\{e,f\}\) so that \(G-e-f\) is matching covered and bipartite; such a pair \(\{e,f\}\) is a removable doubleton. (Each of \(K_4\) and the triangular prism \(\overline{C_6}\) has three removable doubletons.) \textit{M. H. de Carvalho} et al. [ibid. 85, No. 1, 59--93 (2002; Zbl 1024.05071)] proved a conjecture of Lovász which states that every brick, distinct from \(K_4, \overline{C_6}\) and the Petersen graph, has a \(b\)-invariant edge. A cubic graph is essentially \(4\)-edge-connected if it is \(2\)-edge-connected and if its only \(3\)-cuts are the trivial ones; it is well-known that each such graph is either a brick or a brace; we provide a graph-theoretical proof of this fact. We prove that if \(G\) is any essentially \(4\)-edge-connected cubic brick then its edge-set may be partitioned into three (possibly empty) sets: (i) edges that participate in a removable doubleton, (ii) \(b\)-invariant edges, and (iii) quasi-\(b\)-invariant edges; our main theorem states that if \(G\) has two adjacent quasi-\(b\)-invariant edges, say \(e_1\) and \(e_2\), then either \(G\) is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of \(G\) (distinct from \(e_1\) and \(e_2)\) is \(b\)-invariant. As a corollary, we deduce that each essentially \(4\)-edge-connected cubic non-near-bipartite brick \(G\), distinct from the Petersen graph, has at least \(|V(G)| b\)-invariant edges.

Recommendations

• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• Bicritical graphs without removable edges
• Removable edges in near-bricks
• Generating bricks

Cites work

• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• A characterisation of Pfaffian near bipartite graphs
• A characterization of convertible (0,1)-matrices
• A generalization of Little's theorem on Pfaffian orientations
• A new lower bound on the number of perfect matchings in cubic graphs
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• Brick decompositions and the matching rank of graphs
• Ear-decompositions of matching-covered graphs
• Graph theory
• House of Graphs: a database of interesting graphs
• How to build a brick
• scientific article; zbMATH DE number 13859 (Why is no real title available?)
• Matching structure and the matching lattice
• Matching theory
• Minimally non-Pfaffian graphs
• 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 two unsolved problems concerning matching covered graphs
• Optimal ear decompositions of matching covered graphs and bases for the matching lattice
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• The Factorization of Linear Graphs
• The perfect matching polytope and solid bricks

Cited in

(18)

• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On cycle-nice claw-free graphs
• Bicritical graphs without removable edges
• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• Disjoint odd cycles in cubic solid bricks
• The cubic vertices of minimal bricks
• Removable edges in near-bricks
• A characterization of nonfeasible sets in matching covered graphs
• Some snarks are worse than others
• Removable Edges in Claw-Free Bricks
• Extremal spectral radius and essential edge-connectivity
• Thin edges in cubic braces
• Removable edges in near-bipartite bricks
• Thin edges in claw-free bricks
• Nice vertices in cubic graphs
• Claw-free minimal matching covered graphs
• Independent removable edges in cubic bricks

Describes a project that uses

Uses Software

• SageMath
• House of Graphs

This page was built for publication: On essentially 4-edge-connected cubic bricks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290348)