WorksMathematics
Claw-free minimal bricks
Abstract
A graph is called a brick if it is -connected and has a perfect matching for every pair of distinct vertices . 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 . Plummer proved that every -connected claw-free graph of even order is a brick. In this paper, we completely characterize all claw-free minimal bricks. Apart from and the six-vertex wheel , they are precisely the line graphs of graphs obtained from loopless -edge-connected cubic multigraphs by subdividing every edge outside a matching of even size exactly once. Consequently, every claw-free minimal brick of order contains at least cubic vertices and at least 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 , deleting an edge leaves a matching covered graph if and only if the edge lies in a triangle.