ウォーク正則グラフ

グラフ理論において、ウォーク正則グラフとは、頂点からそれ自身への任意の長さの閉路の数が頂点の選択にのみ依存し、頂点の選択には依存しない単純なグラフです。 ^{[1]ウォーク正則グラフは}、頂点推移グラフのスペクトルグラフ理論における類似物と考えることができます。ウォーク正則グラフは必ずしも対称性が高いわけではありませんが、すべての頂点はグラフのスペクトル特性に関して同じように振る舞います ${\displaystyle \ell}$ ${\displaystyle \ell}$

同値な定義

が単純グラフであると仮定します。の隣接行列を、の頂点集合を、すべての に対する頂点削除部分グラフの特性多項式を とします。すると、以下は同値です ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle \Phi_{Gv}(x)}$ ${\displaystyle Gv}$ ${\displaystyle v\in V(G).}$

• ${\displaystyle G}$ はウォーク正則です。
• ${\displaystyle A^{k}}$ はすべての定数対角行列です。${\displaystyle k\geq 0.}$
• ${\displaystyle \Phi _{G-u}(x)=\Phi _{G-v}(x)}$ すべての${\displaystyle u,v\in V(G).}$

例

• 頂点推移グラフはウォーク正則です。^[2]
• 距離正則グラフはウォーク正則である。^{[1]より一般的には、同次}コヒーレント代数における任意の単純グラフはウォーク正則である。
• 連結正則グラフがウォーク正則グラフと呼ばれるのは、最大で4つの異なる固有値を持つ場合である。^[2]

性質

• ウォーク正則グラフは、任意の頂点から始まる長さ2の閉ウォークの数がその頂点の次数の2倍であるため、必然的に正則グラフとなる。^[1]
• ウォーク正則グラフの補グラフはウォーク正則である。^[3]
• ウォーク正則グラフの直積はウォーク正則である。^[3]
• ウォーク正則グラフのカテゴリカル積はウォーク正則である。^[3]
• ウォーク正則グラフの強積はウォーク正則である。^[3]
• 一般に、ウォーク正則グラフの折れ線グラフはウォーク正則ではありません。

k-ウォーク正則グラフ

グラフが-ウォーク正則であるとは、任意の2つの頂点と距離に対して、最大で からまでの長さのウォークの数がとのみに依存する場合である。^{[1] [4]}${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle k,}$ ${\displaystyle \ell }$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle k}$ ${\displaystyle \ell }$

-ウォーク正則グラフのクラスは、ウォーク正則グラフのクラスと全く同じである。 ${\displaystyle 0}$

ウォーク正則グラフが頂点推移グラフを一般化するのと同様に、1ウォーク正則グラフは対称グラフ、つまり頂点推移と辺推移の両方のグラフを一般化するものと考えることができます。例えば、ホフマングラフは1ウォーク正則ですが、対称ではありません。

がグラフの直径以上であれば、 -ウォーク正則グラフは距離正則グラフと一致する。実際、 であり、グラフの固有値が最大で の多重度（とを除く。ここではグラフの次数）であれば、グラフは既に距離正則である。^[5]${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle -d}$ ${\displaystyle d}$

参考文献

1. Dalfó, C.; Fiol, MA; Garriga, E. (2009). 「k-ウォーク正則グラフについて」. Electronic Journal of Combinatorics . 16 (1): #R47. doi : 10.37236/ 136
2. Brouwer, Andries E.; Haemers, Willem H. (2012)、「固有値の少ないグラフ」、Spectra of Graphs (PDF)、Universitext、ニューヨーク、NY: Springer、pp.  217– 218、doi :10.1007/978-1-4614-1939-6、ISBN 978-1-4614-1939-6
3. Godsil, CD; McKay, BD (1980年4月). 「ウォーク正則グラフの存在のための実現可能性条件」.線型代数とその応用. 30 : 51–61 . doi :10.1016/0024-3795(80)90180-9
4. Dalfó, C.; Fiol, MA; Garriga, E. (2009年8月). 「k-ウォーク正則グラフにおけるt-クリークについて」.離散数学電子ノート. 34 : 579–584 . doi :10.1016/j.endm.2009.07.096. hdl : 2117/10784 .
5. Cámara, Marc; van Dam, Edwin R.; Koolen, Jack H.; Park, Jongyook (2013年11月). 「2-ウォーク正則グラフの幾何学的側面」.線形代数とその応用. 439 (9): 2692– 2710. arXiv : 1304.2905 . doi :10.1016/j.laa.2013.07.028.