A Characterization of the degree sequences of 2‐trees |
| |
| Authors: | Prosenjit Bose Vida Dujmović Danny Krizanc Stefan Langerman Pat Morin David R Wood Stefanie Wuhrer |
| |
| Institution: | 1. School of Computer Science Carleton University, Ottawa, Canada;2. Department of Mathematics and Computer Science Wesleyan University, Middletown, Connecticut;3. Chercheur Qualifié DU FNRS DéPartement D'Informatique Université Libre de Bruxelles, Brussels, Belgium;4. Departament de Matem?TICA Aplicada II Universitat Polit?CNICA de Catalunya, Barcelona, Spain |
| |
| Abstract: | A graph G is a 2‐tree if G = K3, or G has a vertex v of degree 2, whose neighbors 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. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008 |
| |
| Keywords: | degree sequence graphical degree sequence 2‐tree k‐tree series‐parallel graph treewidth |
|
|
