Rank‐width of random graphs |
| |
Authors: | Choongbum Lee Joonkyung Lee Sang‐il Oum |
| |
Affiliation: | 1. Department of Mathematics UCLA, , California 90095, Los Angeles;2. Department of Mathematical Sciences, , Kaist, Daejeon 305‐701, Republic of Korea |
| |
Abstract: | 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) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , 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 c81, 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]. © 2011 Wiley Periodicals, Inc. J Graph Theory. |
| |
Keywords: | rank‐width tree‐width clique‐width random graph sharp threshold |
|
|