ゴールデンウィークなので黄金比とグラフ理論の話をします

こんにちは！ゴールデンウィーク、満喫してますか？

ゴールデンウィークを満喫している人、素晴らしいですね！ゴールデンウィークも仕事という人、いつもありがとうございます。

さて、ゴールデンウィークといえば黄金、黄金といえば黄金比ですね。最近黄金比とグラフ理論の関係を知ったので、紹介しようと思います。

グラフの固有値
#

グラフ $G$ は頂点の集合と辺の集合の組 $(V,E)$ で表現する方法の他に、隣接行列を使う方法があります。頂点の番号を $1,2,\ldots,n$ としたとき、隣接行列の $(i,j)$ 成分は、頂点 $i,j$ を結ぶ辺があるとき $1$ 、そうでないとき $0$ です。例えば

○―○―○―○

というパスグラフを考えると、隣接行列は

\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}

です。この行列の固有値を計算すると

\frac{\pm1 \pm\sqrt{5}}{2}

となります。黄金比だ～～～～～！！！！！

グラフの隣接行列の固有値のことを短縮してグラフの固有値と呼びます。グラフ理論を線形代数を使って研究できます。この分野はスペクトルグラフ理論と呼ばれており、私も非常に気になっています。

グラフの固有値を昇順に並べたものを $\lambda_1\ge\lambda_2\ge\cdots\ge \lambda_n$ とします。2 番目に大きい固有値 $\lambda_2$ がスペクトルグラフ理論では重要だそうです。なぜかはわかりません。

$\lambda_2 \le \frac{\sqrt{5}-1}{2}$ をみたすグラフについては

Cvetković, Dragoš; Simić, Slobodan, On graphs whose second largest eigenvalue does not exceed $(\sqrt{5}-1)/2$ . Discrete Math., 138: 213-227, 1995.

に書かれているようです。が、アクセス権がないので読めませんでした。zbMATH のレビューによれば、このようなグラフは

とのことです。3. についてはもう少しいろいろと書かれているそうです。

ここで紹介したもの以外にも、黄金比はグラフ理論に現れるようです。

Saeid Alikhani, Nima Ghanbari. Golden ratio in graph theory: A survey. arXiv:2407.15860

にいろいろ書いてあります。ゴールデンウィークなので読んでみませんか？