On minimally 5-contraction critical graphs
by
Kiyoshi Ando
University of Electro-Communications
Coauthors: Ken-ichi Kawarabayashi (Kei-O University, Vanderbilt University), Atsusi Kaneko (Kogakuin University)

A k-connected graph is said to be k-contraction critical if the contraction of every edge results in a (k-1)-connected graph. An edge of k-connected graph is said to be contraction (or removal) trivial if the contraction (or removal) of the edge results in a graph with minimum degree (k-1). We show that if a minimally 5-contraction critical graph G has neither a contraction trivial edge nor a removal trivial edge then each component of G-V₅ is a star where V₅ is the set of vertices of degree 5.

Date received: April 17, 2001