Rank‐width of random graphs
In: Journal of Graph Theory, Jg. 70 (2012-07-01), Heft 3, S. 339-347
Online
serialPeriodical
Zugriff:
Rank‐widthof 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/nand c>1, then rw(G(n, p))⩾rnfor some r= r(c), and (iv) if p⩽c/nand c81, then rw(G(n, p))⩽2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in nwhenever p= c/nfor each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.
Titel: |
Rank‐width of random graphs
|
---|---|
Autor/in / Beteiligte Person: | Lee, Choongbum ; Lee, Joonkyung ; Oum, Sang‐il |
Link: | |
Zeitschrift: | Journal of Graph Theory, Jg. 70 (2012-07-01), Heft 3, S. 339-347 |
Veröffentlichung: | 2012 |
Medientyp: | serialPeriodical |
ISSN: | 0364-9024 (print) ; 1097-0118 (print) |
DOI: | 10.1002/jgt.20620 |
Sonstiges: |
|