距離正規グラフ

数学のグラフ理論の分野において、距離正則グラフとは、任意の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 k}$${\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 2}$

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

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

3次距離正則グラフは完全に分類されました。

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

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