MMN-347
A sharp threshold for rainbow connection in small-world networks
Y. Shang;Abstract
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 = sqrt(ln n/n) is a sharp threshold function for the property rc(S(n, p,H)) ≤ 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.
Vol. 13 (2012), No. 2, pp. 493-497