Isometric cycles, cutsets, and crowning of bridged graphs

✍ Scribed by Tao Jiang; Seog-Jin Kim; Douglas B. West

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 103 KB
• Volume: 43
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10110

✦ Synopsis

Abstract

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d~G~(x,y) < d~C~(x,y). A cycle C is isometric if d~G~(x,y) = d~C~(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d~G~(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003