✦ LIBER ✦

The largest induced tree in a sparse random graph

✍ Scribed by W. Fernandez de la Vega

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 192 KB
Volume: 9
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<93::aid-rsa6>3.0.co;2-6

No coin nor oath required. For personal study only.

✦ Synopsis

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently large, then the largest size of an induced tree in G(n, p ) , p = c / n , is almost always at least +(log c -log log c -1). The proof relies heavily on a theorem of Frieze concerning the independence number of a sparse random graph. 0 1996 John Wiley & Sons. Inc.

The author proved in 1986 (see [2]) the following theorem.

Theorem 1. For c > 1 the random graph G(n, p ) on n vertices and with edge probability p = cln, contains almost always an induced tree on at least a,.n(lo( 1)) vertices, where ac is the positive root of the equation ca = log( 1 + c2a).

📜 SIMILAR VOLUMES

The largest tree in certain models of ra

The largest tree in certain models of random forests

✍ Ljuben Mutafchiev 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB 👁 2 views

We consider four families of forests on n vertices: labeled and unlabeled forests containing rooted and unrooted trees, respectively. A forest is chosen uniformly from one of the given four families. The limiting distribution of the size of its largest tree is then studied as n ª ϱ. Convergences to

Remarks on the placeability of isomorphi

Remarks on the placeability of isomorphic trees in a complete graph

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G

Calculating the number of spanning trees

Calculating the number of spanning trees in a labeled planar molecular graph whose inner dual is a tree

✍ P. E. John; R. B. Mallion 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 496 KB 👁 1 views

The quantum mechanical relevance of the concept of a spanning tree extant within a given molecular graph-specifically, one that may be considered to represent the carbon-atom connectivity of a particular (planar) conjugated system-was first explicitly pointed out by Professor Roy McWeeny in his now-

On the diameter ofi-center in a graph wi

On the diameter ofi-center in a graph without long induced paths

✍ Dong, Jinquan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

A graph G is said to be P t -free if it does not contain an induced path on t vertices. The i-center C i (G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, t/2 ≤ i ≤ t -2, with the property that, in every c

The daughter from a wishing tree: Unusual Tales about Women in Mythology

✍ Murty, Sudha 📂 Fiction 📅 2019 🏛 Penguin Random House India Private Limited 🌐 English ⚖ 2 MB 👁 1 views

The daughter from a wishing tree: Unusual Tales about Women in Mythology

✍ Sudha Murty 📂 Fiction 📅 2019 🏛 Penguin Random House India Private Limited 🌐 English ⚖ 2 MB 👁 1 views

Did you know that the Trinity often turned to goddesses to defeat the asuras? Did you know that the first clone in the world was created by a woman? The women in Indian mythology might be fewer in number, but their stories of strength and mystery in the pages of ancient texts and epics are many.