Contents

-

Graphs of Diameter at Most Two

Hong-Jian Lai1
1Department of Mathematics West Virginia University Morgantown, WV 26506

Abstract

A graph H is \underline{collapsible} if for every even subset WV(H), H has a spanning connected subgraph whose set of odd-degree vertices is W. In a graph G, there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Reduced graphs have been shown to be useful in the study of supereulerian graphs, hamiltonian line graphs, and double cycle covers, (see[2], [3], [4] [6] ), among others. It has been noted that subdividing an edge of a collapsible graph may result in a noncollapsible graph. In this note we characterize the reduced graphs of elementary subdivision of collapsible graphs of diameter at most two. We also obtain a converse of a result of Catlin [3] when restricted to graphs of diameter at most two. The main result is used to study some hamiltonian property of line graphs.