2009/07/31 by Yong Gao, Gao, Yong
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.0907.5481
arxiv created 2009/07/31 · arxiv updated 2009/12/01
We prove that the treewidth of an Erdös-Rényi random graph \rgn, m is, with high probability, greater than βn for some constant β> 0 if the edge/vertex ratio (m)/(n) is greater than 1.073. Our lower bound (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 gate matrix layout problem. For scale-free random graphs based on the Barabá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.