正則グラフ
あるグラフの隣接行列を A とする。そのグラフが正則であることは、A の固有ベクトルが j = ( 1 , ... , 1 ) {\displaystyle {\textbf {j}}=(1,\dots ,1)} であることと同値である。その場合、その固有値はそのグラフの次数となる。他の固有値に対応した固有ベクトルは j {\displaystyle {\textbf {j}}} と直交なので、そのような固有ベクトル v = ( v 1 , ... , v n ) {\displaystyle v=(v_{1},\dots ,v_{n})} について ∑ i = 1 n v i = 0 {\displaystyle \sum _{i=1}^{n}v_{i}=0} が成り立つ。
次数 k の正則グラフが連結していることと、固有値 k の重複度が1であることは同値である。
正則な連結グラフの判定基準も存在する。
1 2 Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
↑ Regular Graphs M. Meringer, J. Graph Theory, 1999, 30, 137.