スペクトルグラフ理論

数学において、スペクトルグラフ理論は、隣接行列もしくはラプラシアン行列のような、そのグラフに結びついた行列の固有方程式、固有値、固有ベクトルに関係する、グラフの性質の研究である。

単純グラフの隣接行列は、実な対称行列であり、したがってであり；その固有値は実な代数的整数である。

頂点の名称付けによってその隣接行列が変わるのにたいして、それのスペクトルは、完全ではないものの、ひとつのである。

スペクトルグラフ理論は、のような、そのグラフと結びついた行列の固有値の重複度を通して定義される、グラフのパラメーターとも関係する。

共スペクトルグラフ 

もし二つのグラフの隣接行列の固有値の多重集合が等しいならば、それらの二つのグラフは共スペクトル（）あるいは等スペクトル（）であると呼ばれる。

二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。

共スペクトルグラフを探すこと 

木は共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。

正則グラフの一対は、それらの補グラフが共スペクトルであるときにかぎり、共スペクトルである。

もしそれらが等しい交点配列（）を有するときに限り、一対のは共スペクトルである。

共スペクトルグラフはによっても構成されうる。

共スペクトルグラフのその他の重要な根拠としてはの、点-共線形グラフ（）と直線-交点グラフがある。これらのグラフは常に共スペクトルである、しかししばしばグラフ同型ではない。

関連項目 

 
 強正則グラフ
 
 
 代数的グラフ理論

脚注または引用文献

ウェブサイト

書籍

雑誌

参考文献

外部リンク