Rank-width of random graphs

DOI10.1002/JGT.20620MaRDI QIDQ2897211zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Joonkyung Lee, Sang-Il Oum

Publication date 10 July 2012

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.0461

zbMATH Keywords

random graphclique-widthrank-widthsharp thresholdtree-width

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Abstract: 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<p<1 is a constant, then rw(G(n,p)) = lceil n/3 ceil-O(1), (ii) if 1/n<< p <1/2, then rw(G(n,p))= lceil n/3 ceil-o(n), (iii) if p = c/n and c > 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).

Recommendations

• On the tree-depth of random graphs
• The rank of random graphs
• A note on treewidth in random graphs
• Publication:4864308
• On the treewidth and related parameters of random geometric graphs

Cites work

• Approximating clique-width and branch-width
• Expander graphs and their applications
• Graph minors. III. Planar tree-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the Threshold of Having a Linear Treewidth in Random Graphs
• Rank‐width is less than or equal to branch‐width
• Treewidth. Computations and approximations
• Upper bounds to the clique width of graphs

Cited in

(21)

• On the tree-depth and tree-width in heterogeneous random graphs
• Nordhaus-Gaddum for treewidth
• Large hypertree width for sparse random hypergraphs
• The rank-width of the square grid
• On the Boolean-width of a graph: structure and applications
• On treewidth and related parameters of random geometric graphs
• Boolean-width of graphs
• scientific article; zbMATH DE number 867648 (Why is no real title available?)
• On giant components and treewidth in the layers model
• On the treewidth and related parameters of random geometric graphs
• Rank-width: algorithmic and structural results
• Twin-width of random graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Bounds for the twin-width of graphs
• On the tree-depth of random graphs
• Fractional edge cover number of Model RB
• A note on the width of sparse random graphs
• The Minrank of Random Graphs
• Distribution of coefficients of rank polynomials for random sparse graphs
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• Expected values of parameters associated with the minimum rank of a graph

This page was built for publication: Rank-width of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897211)