Graphs of Diameter at Most Two

A graph \(H\) is \underline{collapsible} if for every even subset \(W \subseteq V(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.