A characterization of the degree sequences of 2-trees

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

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 proceeding › Conference Paper › Research › peer-review

Abstract

A graph G is a 2-tree if G = K₃ 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 language	English
Title of host publication	Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Pages	232-241
Number of pages	10
Publication status	Published - 22 Aug 2007
Externally published	Yes
Event	9th 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 2007 → 6 Jan 2007

Conference

Conference	9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Country/Territory	United States of America
City	New Orleans, LA
Period	6/01/07 → 6/01/07

Keywords

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

Cite this

@inproceedings{c0e0b6bc534f42a99acc199abe71d422,

title = "A characterization of the degree sequences of 2-trees",

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.",

keywords = "2-tree, Degree sequence, Graphical degree sequence, K-tree, Series-parallel graph, Treewidth",

author = "Prosenjit Bose and Vida Dujmovi{\'c} and Danny Krizanc and Stefan Langerman and Pat Morin and Wood, {David R.} and Stefanie Wuhrer",

year = "2007",

month = aug,

day = "22",

language = "English",

isbn = "0898716284",

pages = "232--241",

booktitle = "Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics",

note = "9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics ; Conference date: 06-01-2007 Through 06-01-2007",

}

Bose, P, Dujmović, V, Krizanc, D, Langerman, S, Morin, P, Wood, DR & Wuhrer, S 2007, A characterization of the degree sequences of 2-trees. in Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics. pp. 232-241, 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, New Orleans, LA, United States of America, 6/01/07.

A characterization of the degree sequences of 2-trees. / Bose, Prosenjit; Dujmović, Vida; Krizanc, Danny et al.

Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics. 2007. p. 232-241.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A characterization of the degree sequences of 2-trees

AU - Bose, Prosenjit

AU - Dujmović, Vida

AU - Krizanc, Danny

AU - Langerman, Stefan

AU - Morin, Pat

AU - Wood, David R.

AU - Wuhrer, Stefanie

PY - 2007/8/22

Y1 - 2007/8/22

N2 - 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.

AB - 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.

KW - 2-tree

KW - Degree sequence

KW - Graphical degree sequence

KW - K-tree

KW - Series-parallel graph

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=34547959895&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:34547959895

SN - 0898716284

SN - 9780898716283

SP - 232

EP - 241

BT - Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics

T2 - 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics

Y2 - 6 January 2007 through 6 January 2007

ER -

A characterization of the degree sequences of 2-trees

Abstract

Conference

Keywords

Other files and links

Cite this