A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that dG(x,y) < dC(x,y). A cycle C is isometric if dG(x,y) = dC(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 dG(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
['Tao Jiang', 'Seog-Jin Kim', 'Douglas B. West']
Isometric cycles, cutsets, and crowning of bridged graphs