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.

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

• scientific article; zbMATH DE number 13859 (Why is no real title available?)
• A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian 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
• 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
• 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
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks

Cited in

(14)

• Bicritical graphs without removable edges
• Disjoint odd cycles in cubic solid bricks
• On cycle-nice claw-free graphs
• Some snarks are worse than others
• Removable edges in near-bricks
• Extremal spectral radius and essential edge-connectivity
• The cubic vertices of minimal bricks
• Removable Edges in Claw-Free Bricks
• A characterization of nonfeasible sets in matching covered graphs
• Removable edges in near-bipartite bricks
• Thin edges in cubic braces
• 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
• \(b\)-invariant edges in essentially 4-edge-connected near-bipartite 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)