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.

Additional Metadata
Keywords 2-tree, Degree sequence, Graphical degree sequence, K-tree, Series-parallel graph, Treewidth
Conference 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Citation
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.