1-1hit |
Kotaro NAKAGAWA Hiroki YAMAGUCHI
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 with high probability.