✦ LIBER ✦

A Characterization of the degree sequences of 2-trees

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

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 260 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20302

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G is a 2‐tree if G = K~3~, 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

📜 SIMILAR VOLUMES

On low bound of degree sequences of span

On low bound of degree sequences of spanning trees inK-edge-connected graphs

✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.

The 2-intersection number of paths and b

The 2-intersection number of paths and bounded-degree trees

✍ Michael S. Jacobson; André E. Kézdy; Douglas B. West 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 416 KB 👁 1 views

## Abstract We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The __2‐intersection number__ θ~2~(__G__) of a graph __G__ is the minimum size of the union of sets in such a representatio

Multiset Permutations and Loopless Gener

Multiset Permutations and Loopless Generation of Ordered Trees with Specified Degree Sequence

✍ James F. Korsh; Paul LaFollette 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 131 KB

An ordered tree with specified degree sequence and n internal nodes has a i Ž . nodes of degree i, where a s 1 q Ý i y 1 a and n s Ý a . This paper presents the first loopless algorithm for generating all ordered trees with specified degree sequence. It uses a new version of the algorithm for gener

A characterization of (γ, i)-trees

✍ E. J. Cockayne; O. Favaron; C. M. Mynhardt; J. Puech 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB

Characterization of a Branch of the Phyl

Characterization of a Branch of the Phylogenetic Tree

✍ STUART A. SAMUEL; GEZHI WENG 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 287 KB

We use a combination of analytic models and computer simulations to gain insight into the dynamics of evolution. Our results suggest that certain interesting phenomena should eventually emerge from the fossil record. For example, there should be a "tortoise and hare effect": those genera with the sm

The distribution of nodes of given degre

The distribution of nodes of given degree in random trees

✍ Drmota, Michael; Gittenberger, Bernhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 391 KB 👁 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ µ k n and variance ∼ σ 2 k n with positive constants µ