Solid bricks that every b-invariant edge is solitary

2025/07/29 by Zhang, Yipei, Wang, Xiumei
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.21565

Abstract

A graph G is a brick if it is 3-connected and G-\u,v\ has a perfect matching for any two distinct vertices u and v of G. A brick G is solid if for any two vertex disjoint odd cycles C₁ and C₂ of G, G-(V(C₁)∪ V(C₂)) has no perfect matching. Lucchesi and Murty proposed a problem concerning the characterization of bricks, distinct from K₄, C₆ and the Petersen graph, in which every b-invariant edge is solitary. In this paper, we show that for a solid brick G of order n that is distinct from K₄, every b-invariant edge of G is solitary if and only if G is a wheel W_n.

Citations

• Cubic bricks that every b-invariant edge is forcing
• b-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
• On essentially 4-edge-connected cubic bricks

Related

• Claw-free bricks that every b-invariant edge is solitary
• Cubic bricks that every b-invariant edge is forcing
• Bricks and conjectures of Berge, Fulkerson and Seymour
• Generating Near-Bipartite Bricks
• b-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks