betaFeedback

WorksMathematics

Claw-free minimal bricks

Abstract

A graph GG is called a brick if it is 33-connected and G−{u,v}G-\{u,v\} has a perfect matching for every pair of distinct vertices u,v∈V(G)u,v\in V(G). A brick is minimal if deleting any edge results in a graph that is no longer a brick. A graph is claw-free if it contains no induced K1,3K_{1,3}. Plummer proved that every 33-connected claw-free graph of even order is a brick. In this paper, we completely characterize all claw-free minimal bricks. Apart from K4K_4 and the six-vertex wheel W5W_5, they are precisely the line graphs of graphs obtained from loopless 33-edge-connected cubic multigraphs by subdividing every edge outside a matching of even size exactly once. Consequently, every claw-free minimal brick of order nn contains at least 4n/54n/5 cubic vertices and at least 4n/54n/5 edges joining cubic vertices. Both bounds are sharp. This establishes the conjectures of Norine and Thomas and of Lovász for claw-free minimal bricks in sharp quantitative forms. We also show that, for a claw-free minimal brick of order at least 88, deleting an edge leaves a matching covered graph if and only if the edge lies in a triangle.

Paper details

vlnc:W_5ewbsu3m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…