UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Rank-width of random graphs

Lee, C; Lee, J; Oum, S-I; (2012) Rank-width of random graphs. Journal of Graph Theory , 70 (3) pp. 339-347. 10.1002/jgt.20620. Green open access

[img]
Preview
Text
rankwidth.pdf - Accepted version

Download (156kB) | Preview

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 urn:x-wiley:03649024:jgt20620:equation:jgt20620-math-0001, 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].

Type: Article
Title: Rank-width of random graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1002/jgt.20620
Publisher version: https://doi.org/10.1002/jgt.20620
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10120245
Downloads since deposit
2Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item