✦ LIBER ✦

Rank-width of random graphs

✍ Scribed by Choongbum Lee; Joonkyung Lee; Sang-il Oum

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

No coin nor oath required. For personal study only.

✦ Synopsis

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514-528]. We investigate the asymptotic behavior of rank-width of a random graph G(n, p). We show that, asymptotically almost surely, (i

2 ), then rw(G(n, p)) = 1 / 3 -o(n), (iii) if p = c / n and c>1, then rw(G(n, p)) ≥ rn for some r = r(c), and (iv) if p ≤ c / n and c<1, then rw(G(n, p)) ≤ 2. As a corollary, we deduce that the tree-width of G(n, p) is linear in n whenever p = c / n for each c>1, answering a question of Gao [2006].

📜 SIMILAR VOLUMES

The plane-width of graphs

✍ Marcin Kamiński; Paul Medvedev; Martin Milanič 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane-width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane-wid

Rank-width is less than or equal to bran

Rank-width is less than or equal to branch-width

✍ Sang-il Oum 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract We prove that the rank‐width of the incidence graph of a graph __G__ is either equal to or exactly one less than the branch‐width of __G__, unless the maximum degree of __G__ is 0 or 1. This implies that rank‐width of a graph is less than or equal to branch‐width of the graph unless the

Tree-width and circumference of graphs

✍ Etienne Birmele 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 37 KB

Random trees and random graphs

✍ Tomasz Łuczak 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB 👁 2 views

In the paper we study the asymptotic behavior of the number of trees with n Ž . Ž . vertices and diameter k s k n , where n y k rnª a as n ª ϱ for some constant a-1. We use this result to determine the limit distribution of the diameter of the random graph Ž .

On the rank of random matrices

✍ C. Cooper 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 2 views

Let M = m ij be a random n × n matrix over GF(2). Each matrix entry m ij is independently and identically distributed, with Pr m ij = 0 = 1 -p n and Pr m ij = 1 = p n . The probability that the matrix M is nonsingular tends to c 2 ≈ 0 28879 provided min p 1 -p ≥ log n + d n /n for any d n → ∞. Sharp

Random interval graphs

✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o