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 / \sqrt{c-d+1} \}$ with high probability.

著者

• YAMAGUCHI Hiroki

  Dept. of Civil & Environmental Eng., Saitama University

• YAMAGUCHI Hiroki

  Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology

• NAKAGAWA Kotaro

  Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology

• NAKAGAWA KOTARO

  Dept. of Math. and Computer Science, Tokyo Inst. of Technology

関連論文

• Characterization of Galloping Based on Field Data Observed in Tsuruga Test Line
• The First Eigenvalue of (c,d)-Regular Graph
• An O(n^)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

スポンサーリンク