A characterization of the degree sequences of 2-trees

Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin, David R. Wood, Stefanie Wuhrer

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Pages232-241
Number of pages10
Publication statusPublished - 22 Aug 2007
Externally publishedYes
Event9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States of America
Duration: 6 Jan 20076 Jan 2007

Conference

Conference9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Country/TerritoryUnited States of America
CityNew Orleans, LA
Period6/01/076/01/07

Keywords

  • 2-tree
  • Degree sequence
  • Graphical degree sequence
  • K-tree
  • Series-parallel graph
  • Treewidth

Cite this