科研之友
微信
新浪微博
Facebook
分享链接
摘要
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. We prove that p = root ln n/n is a sharp threshold function for the property rc(S(n, p, H)) %26lt;= 2 in the small-world networks. As by-products, our extension of the concept of independence in graph theory and generalized small-world network models are of independent interest.
- 出版日期2012
