Mathematics – Combinatorics
Scientific paper
2010-01-04
Mathematics
Combinatorics
10 pages
Scientific paper
Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymptotic behavior of rank-width of a random graph G(n,p). We show that, asymptotically almost surely, (i) if 0
1, then rw(G(n,p)) > r n 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 G(n,p) has linear tree-width whenever p=c/n for each c>1, answering a question of Gao (2006).
Lee Choongbum
Lee Joonkyung
Oum Sang-il
No associations
LandOfFree
Rank-width of Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rank-width of Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rank-width of Random Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-6835