［参］細矢治夫「トポロジカル・インデックス」日本評論社

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】トポロジカル・インデックス

　グラフＧが与えられたとき，互いに隣接しない（頂点を共有しない）ｋ本の辺を選ぶ組み合わせ数を，非隣接数ｐ（Ｇ，ｋ）と定義する．ｐ（Ｇ，０）＝１，ｐ（Ｇ，０）＝ｅ（辺の数）．

　非隣接数ｐ（Ｇ，ｋ）の総和をトポロジカル・インデックスＺGと定義する．

　　ＺG＝Σｐ（Ｇ，ｋ）　　　（ｋ＝０〜［ｎ／２］）

　また，非隣接数ｐ（Ｇ，ｋ）の母関数

　　ＱG（ｘ）＝Σｐ（Ｇ，ｋ）ｘ^k　　　（ｋ＝０〜［ｎ／２］）

を定義すると，ＱG（ｘ）＝ＺGが得られる．

　特性多項式は隣接行列Ａを用いて

　　ＰG（ｘ）＝（−１）^nｄｅｔ｜Ａ−ｘＥ｜

で定義される．証明は当該書籍に譲るが，・・・

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］Ｇ＝Ｐn（経路グラフ）のとき，ＺG＝ｆn（フィボナッチ数のＺグラフは経路グラフである）

　　ｐ（Ｇ，ｋ）＝（ｎ−ｋ，ｋ）

　　ＺG＝Σｐ（Ｇ，ｋ）＝ｆn

　　ＰG（ｘ）＝Ｓn

［２］Ｇが一般の木グラフのとき

　　ＰG（ｘ）＝Σ（−１）^kｐ（Ｇ，ｋ）ｘ^(n-2k)

　　ＺGは特性多項式の係数の絶対値の総和で与えられる．

　　グラフが大きくなると非隣接数ｐ（Ｇ，ｋ）を求める計算時間は増大（組み合わせ論的爆発）するが，木グラフについてはそれを避けることができる．

［３］Ｇが櫛グラフのとき，ペル数のＺグラフは櫛グラフである＝櫛グラフのトポロジカル・インデックスはペル数である．

［４］Ｇが単環グラフのとき，ＺG＝Ｌn（リュカ数のＺグラフは単環グラフである．

　　ｐ（Ｇ，ｋ）＝（ｎ−ｋ，ｋ）ｎ／（ｎ−ｋ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝