The First Eigenvalue of (c, d)-Regular Graph

摘要

We show a phase transition of the first eigenvalue of random (c, d)-regular graphs, whose instance of them consists of one vertex with degree c and the other vertices with degree d for c > d. We investigate a reduction from the first eigenvalue analysis of a general (c, d)-regular graph to that of a tree, and prove that, for any fixed c and d, and for a graph G chosen from the set of all (c, d)-regular graphs with n vertices uniformly at random, the first eigenvalue of G is approximately max{d, c/ (√)Vc - d + 1} with high probability.