Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs

Details Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs

2009-07-31

arxiv.org/abs/0907.5481v1

Computer Science

Discrete Mathematics

Scientific paper

We prove that the treewidth of an Erd\"{o}s-R\'{e}nyi random graph $\rg{n, m}$ is, with high probability, greater than $\beta n$ for some constant $\beta > 0$ if the edge/vertex ratio $\frac{m}{n}$ is greater than 1.073. Our lower bound $\frac{m}{n} > 1.073$ improves the only previously-known lower bound. We also study the treewidth of random graphs under two other random models for large-scale complex networks. In particular, our result on the treewidth of \rigs strengths a previous observation on the average-case behavior of the \textit{gate matrix layout} problem. For scale-free random graphs based on the Barab\'{a}si-Albert preferential-attachment model, our result shows that if more than 12 vertices are attached to a new vertex, then the treewidth of the obtained network is linear in the size of the network with high probability.

Affiliated with

Also associated with

No associations

Rating

Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free 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 Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267371