A graph G is a 2-tree if G = K3 or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.

, , , , ,
9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
School of Computer Science

Bose, P, Dujmović, V, Krizanc, D. (Danny), Langerman, S. (Stefan), Morin, P, Wood, D, & Wuhrer, S. (Stefanie). (2007). A characterization of the degree sequences of 2-trees. Presented at the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics.