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

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

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

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

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

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

で定義される.Zが一般の木グラフのとき

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

 特性多項式と密接な関係にあるものに,マッチング多項式

  MG(x)=Σ(−1)^kp(G,k)x^(n-2k)   (k=0〜[n/2])

がある.木グラフに関しては,特性多項式とマッチング多項式は同一であるが,非木グラフの場合,両者は異なる.

 頂点数が偶数2nのグラフGのマッチング多項式の定数項は完全マッチング数K(G)になっていて,切頂20面体ではK(G)=12500である.

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

[1]G=Pn(経路グラフ)のとき,

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

  MG(x)=Sn(x)   (第2種変形チェビシェフ多項式)

[2]Gが単環グラフのとき,

  PG(x)=Σ(−1)^k(n−k,k)n/(n−k)x^(n-2k)=MG(x)−2

  MG(x)=Cn(x)   (第1種変形チェビシェフ多項式)

[3]G=Kn(完全グラフ)のとき,マッチング多項式は変形エルミート多項式に等しい

  MG(x)=hn(x)

また,ヤング図の数は完全グラフKnのトポロジカル・インデックスに等しい.

[4]G=Km,n(2部完全グラフ)のとき,マッチング多項式はラゲール多項式に等しい

  MG(x)=(−1)^mn!x^(m-n)/m!・L(x^2)

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