On essentially 4-edge-connected cubic bricks

DOI10.37236/8594zbMATH Open1431.05123arXiv1803.08713OpenAlexW3002049452MaRDI QIDQ2290348FDOQ2290348

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)

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.

Full work available at URL: https://arxiv.org/abs/1803.08713

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

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

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)

Cites Work

• House of Graphs: a database of interesting graphs
• Graph theory
• Ear-decompositions of matching-covered graphs
• Matching theory
• Optimal ear decompositions of matching covered graphs and bases for the matching lattice
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• Pólya's permanent problem
• A characterization of convertible (0,1)-matrices
• Permanents, Pfaffian orientations, and even directed circuits
• The Factorization of Linear Graphs
• Minimally non-Pfaffian graphs
• Matching structure and the matching lattice
• A characterisation of Pfaffian near bipartite graphs
• Brick decompositions and the matching rank of graphs
• A generalization of Little's theorem on Pfaffian orientations
• A new lower bound on the number of perfect matchings in cubic graphs
• The perfect matching polytope and solid bricks
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs
• How to build a brick
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• On a conjecture of Lovász concerning bricks. II: Bricks of finite characteristic
• On two unsolved problems concerning matching covered graphs
• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks

Cited In (14)

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

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)