✦ LIBER ✦

Vertices of degree k in random unlabeled trees

✍ Scribed by Konstantinos Panagiotou; Makrand Sinha

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 172 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20567

No coin nor oath required. For personal study only.

✦ Synopsis

Let H n be the class of unlabeled trees with n vertices, and denote by H n a tree that is drawn uniformly at random from this set. The asymptotic behavior of the random variable deg k (H n ) that counts vertices of degree k in H n was studied, among others, by Drmota and Gittenberger in [J Graph Theory 31(3) (1999), 227-253], who showed that this quantity satisfies a central limit theorem. This result provides a very precise characterization of the "central region" of the distribution, but does not give any non-trivial information about its tails. In this work, we study further the number of vertices of degree k in H n . In particular, for k = O((log n / (log log n)) 1/2 ) we show exponential-type bounds for the probability that deg k (H n ) deviates from its expectation. On the technical side, our proofs are based on the analysis of a randomized algorithm that generates unlabeled trees in the so-called Boltzmann model. The analysis of such Part of this work was done while visiting ETH Zürich in May-July '08 when Makrand Sinha was an undergraduate student at the

📜 SIMILAR VOLUMES

Vertices of given degree in a random gra

Vertices of given degree in a random graph

✍ Béla Bollobás 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 349 KB 👁 1 views

Balance vertices in trees

✍ Reid, K. B. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

A new notion of balanced bipartitions of the vertices in a tree T is introduced and studied. It gives rise to a new central set of vertices in T, each of which can be considered to be a discrete version of the center of gravity of T. We seek vertices x, called balance vertices, such that the two sum

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 µ

On the number of vertices of given degre

On the number of vertices of given degree in a random graph

✍ Zbigniew Palka 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor

The number of vertices of degree k in a

The number of vertices of degree k in a minimally k-edge-connected digraph

✍ Yuan Xu-dong; Kang Liying; Cai Mao-cheng 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

Let k be a positive integer, and D = (V (D), E(D)) be a minimally k-edge-connected simple digraph. We denote the outdegree and indegree of x ∈ V (D) by δ D (x) and ρ D (x), respectively. Let u + (D) denote the number of vertices W. Mader asked the following question in [Mader, in Paul Erdös is Eigh

The Number of Vertices of Degree k in a

The Number of Vertices of Degree k in a Minimally k-Edge-Connected Graph

✍ M.C. Cai 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 346 KB