AMCA: Isometric Cycles and bridged graphs by Seog-Jin Kim

Atlas Mathematical Conference Abstracts || Conferences | Abstracts | for Organizers | About AMCA

Horizons in Combinatorics/16th Shanks Lecture Series
May 21-24, 2001
Vanderbilt University
Nashville, TN, USA

Organizers
Paul Edelman, Mark Ellingham, Jonathan Farley, Mike Plummer, Jerry Spinrad

Isometric Cycles and bridged graphs
by
Seog-Jin Kim
University of Illinois at Urbana-Champaign
Coauthors: Tao Jiang, Douglas B. West

A graph G is called bridged if every cycle C of length at least 4 has two vertices x and y such that d_G(x, y) < d_C(x, y). We show that every minimal cutset S in a bridged graph G induces a connected subgraph of G. We also 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 minimum cutsets in bridged graphs have diameter at most 2 and settles Jamison's question whether it is true that every minimal cutset in a bridged graph is convex.

Date received: April 17, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cags-28.