スペクトルグラフ理論

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

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

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

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

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

二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。共スペクトルグラフを探すこと木は共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。

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

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

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

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

脚注出典

参考文献

吉田悠一：「スペクトルグラフ理論: 線形代数からの理解を目指して」、サイエンス社(SGCライブラリ190），ISBN 978-4781916019、（2024年3月）. ボグダン・ニカ：「線形代数で考えるスペクトラル・グラフ理論入門」、日本評論社、、（2024年4月）.

Źródło i licencja