3-Trees with Diameter 2

Allan Bickle1
1Department of Mathematics, Purdue University 610 Purdue Mall, West Lafayette, IN 47907 USA

Abstract

A \(k\)-tree is a graph that can be formed by starting with \(K_{k+1}\) and iterating the operation of making a new vertex adjacent to all the vertices of a \(k\)-clique of the existing graph. A structural characterization of 3-trees with diameter at most 2 is proven. This implies a corollary for planar 3-trees which leads to a description of their degree sequences.

Keywords: \(k\)-tree, Diameter, Planar graph, Degree sequence