距離正規分布グラフ

自己同型によって定義されるグラフ族
推移的な距離	→	規則的な距離	←	強正則
↓
対称（弧推移的）	←	t推移的、 t  ≥ 2		歪対称
↓
（連結されている場合） 頂点推移的および辺推移的	→	辺推移的かつ正則的	→	辺推移的
↓		↓		↓
頂点推移的	→	正則	→	（二部の場合） 双正則
↑
ケーリーグラフ	←	ゼロ対称		非対称

グラフ理論という数学の分野において、距離正則グラフとは、任意の2つの頂点vとwについて、 vから距離jにある頂点とwから距離kにある頂点の数が、 j、k 、およびvとwの間の距離のみに依存する正則 グラフです

著者によっては、完全グラフと切断されたグラフをこの定義から除外している人もいます。

すべての距離推移グラフは距離正則である。実際、距離正則グラフは距離推移グラフの組合せ論的一般化として導入され、必ずしも大きな自己同型群を持たなくても、距離推移グラフの数値的正則性特性を持つ。

交差配列

距離正則グラフの交差配列とは、グラフの直径を とし、各 に対して は からの距離にある の近傍の数を与え、は任意の頂点のペアと距離 にある に対してからの距離にある の近傍の数を与えます。また、からの距離にある の近傍の数を与える数もあります。これらの数はグラフの交差数と呼ばれます。これらは次の式を満たします。ここでは任意の頂点の原子価、つまり近傍の数です。 ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ ${\displaystyle d}$ ${\displaystyle 1\leq j\leq d}$ ${\displaystyle b_{j}}$ ${\displaystyle u}$ ${\displaystyle j+1}$ ${\displaystyle v}$ ${\displaystyle c_{j}}$ ${\displaystyle u}$ ${\displaystyle j-1}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle j}$ ${\displaystyle a_{j}}$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle v}$ ${\displaystyle a_{j},b_{j},c_{j}}$ ${\displaystyle a_{j}+b_{j}+c_{j}=k,}$ ${\displaystyle k=b_{0}}$

直径のグラフが距離正則となるのは、それが前述の意味で交差配列を持つ場合のみであることがわかります。 ${\displaystyle G}$ ${\displaystyle d}$

共スペクトルグラフと不連続距離正則グラフ

連結された距離正則グラフのペアは、それらの隣接行列が同じスペクトルを持つ場合、共スペクトル的である。これは、それらのグラフが同じ交差配列を持つことと等価である。

距離正則グラフは、共スペクトル距離正則グラフの 分離和である場合に限り、切断されます。

性質

交差配列を持つ、結合価数 の距離正則グラフを とします。各 について、任意の頂点から 距離 にある頂点の数を、距離にある頂点のペアを関連付けることで形成される隣接行列を持つ 正則グラフをとします ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ ${\displaystyle 0\leq j\leq d,}$ ${\displaystyle k_{j}}$ ${\displaystyle j}$ ${\displaystyle G_{j}}$ ${\displaystyle k_{j}}$ ${\displaystyle A_{j}}$ ${\displaystyle G}$ ${\displaystyle j}$

グラフ理論的性質

• ${\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}$ すべての${\displaystyle 0\leq j<d}$
• ${\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}$ および${\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}$

スペクトル特性

• ${\displaystyle G}$ は異なる固有値を持ちます。${\displaystyle d+1}$
• の唯一の単純固有値は、または が二部である場合はとの両方です${\displaystyle G}$ ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle -k}$ ${\displaystyle G}$
• ${\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}$ が完全な多部グラフでない限り、の任意の固有値の重複度に対して。${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$
• ${\displaystyle d\leq 3m-4}$ がサイクルグラフまたは完全多部グラフでない限り、の任意の固有値の重複度に対して。${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$

が強正則 である場合、 およびとなります。 ${\displaystyle G}$ ${\displaystyle n\leq 4m-1}$ ${\displaystyle k\leq 2m-1}$

連想スキーム

距離正則グラフの -距離隣接行列は連想スキームを形成します ${\displaystyle i}$ ${\displaystyle A_{i}}$ ${\displaystyle i=0,1,...,d}$

例

種数3の有向面に埋め込まれた次数7のクライングラフと関連マップ。このグラフは、交差配列{7,4,1;1,2,7}と自己同型群PGL(2,7)を持つ距離正則グラフです。

距離正則グラフの最初の例としては次のようなものがあります。

• 完全なグラフ。
• サイクルグラフ。
• 奇妙なグラフ。
• ムーアグラフ。
• 正多角形の共線性グラフ。
• ウェルズグラフとシルベスター グラフ。
• 強正則グラフは、直径 2 の距離正則グラフです。

距離正則グラフの分類

与えられた価数を持つ連結距離正則グラフは有限個しか存在しない。^[1]${\displaystyle k>2}$

同様に、任意の固有値多重度を持つ連結された距離正則グラフは有限個しか存在しない^[2]（完全な多部グラフを除く）。 ${\displaystyle m>2}$

3次距離正則グラフ

3次距離正則グラフは完全に分類されています

13 種類の異なる 3 次距離正則グラフは、 K ₄ (または4 面体グラフ)、K _3,3、ピーターセン グラフ、立方体グラフ、ヒーウッド グラフ、パップス グラフ、コクセター グラフ、タット – コクセター グラフ、 12 面体グラフ、デザルググラフ、タット 12 ケージ、ビッグス – スミス グラフ、およびフォスター グラフです。

参考文献

1. Bang, S.; Dubickas, A.; Koolen, JH; Moulton, V. (2015-01-10). 「2より大きい固定原子価の距離正則グラフは有限個しか存在しない」. Advances in Mathematics . 269 (Supplement C): 1– 55. arXiv : 0909.5253 . doi : 10.1016/j.aim.2014.09.025 . S2CID  18869283
2. Godsil, CD (1988-12-01). 「距離正則グラフの直径の境界設定」. Combinatorica . 8 (4): 333– 343. doi :10.1007/BF02189090. ISSN  0209-9683. S2CID  206813795.

さらに読む

• ゴッドシル, C. D. (1993).代数的組合せ論. チャップマン・アンド・ホール数学シリーズ. ニューヨーク: チャップマン・アンド・ホール. ISBN 978-0-412-04131-0 MR  1220704