■細矢インデックス(その3)

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

===================================

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

 グラフGが与えられたとき,互いに隣接しない(頂点を共有しない)k本の辺を選ぶ組み合わせ数を,非隣接数p(G,k)と定義する.p(G,0)=1,p(G,0)=e(辺の数).

 非隣接数p(G,k)の総和をトポロジカル・インデックスZGと定義する.

  ZG=Σp(G,k)   (k=0〜[n/2])

 また,非隣接数p(G,k)の母関数

  QG(x)=Σp(G,k)x^k   (k=0〜[n/2])

を定義すると,QG(x)=ZGが得られる.

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

  PG(x)=(−1)^ndet|A−xE|

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

===================================

[1]G=Pn(経路グラフ)のとき,ZG=fn(フィボナッチ数のZグラフは経路グラフである)

  p(G,k)=(n−k,k)

  ZG=Σp(G,k)=fn

  PG(x)=Sn

[2]Gが一般の木グラフのとき

  PG(x)=Σ(−1)^kp(G,k)x^(n-2k)

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

  グラフが大きくなると非隣接数p(G,k)を求める計算時間は増大(組み合わせ論的爆発)するが,木グラフについてはそれを避けることができる.

[3]Gが櫛グラフのとき,ペル数のZグラフは櫛グラフである=櫛グラフのトポロジカル・インデックスはペル数である.

[4]Gが単環グラフのとき,ZG=Ln(リュカ数のZグラフは単環グラフである.

  p(G,k)=(n−k,k)n/(n−k)

===================================