ウォーク正則グラフ

グラフ理論において、ウォーク正則グラフとは、任意の長さの閉じたウォークの数が${\displaystyle \ell }$頂点からそれ自身への移動は、${\displaystyle \ell }$しかし、頂点の選択には依存しない。^{[ 1 ]}ウォーク正則グラフは、スペクトルグラフ理論における頂点推移グラフの類似物と考えることができる。ウォーク正則グラフは必ずしも非常に対称的ではないが、そのすべての頂点は、グラフのスペクトル特性に関して依然として同一の振る舞いをする。

仮に${\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 \ファイ _{Gu}(x)=\ファイ _{Gv}(x)}$すべての人々のために${\displaystyle u,v\in V(G).}$

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

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

グラフとは${\displaystyle k}$-walk-regular 任意の 2 つの頂点に対して${\displaystyle v}$そして${\displaystyle w}$最大距離​${\displaystyle k,}$長さの散歩の数${\displaystyle \ell }$ から${\displaystyle v}$に${\displaystyle w}$のみに依存する${\displaystyle k}$そして${\displaystyle \ell }$[ ^{1 ] [ 4 ]​}

のクラス${\displaystyle 0}$-ウォーク正則グラフは、まさにウォーク正則グラフのクラスです。

頂点推移グラフを一般化したウォーク正則グラフと同様に、1-ウォーク正則グラフは、頂点推移性と辺推移性の両方を満たす対称グラフを一般化したものと考えることができる。例えば、ホフマングラフは1-ウォーク正則であるが、対称グラフではない。

もし${\displaystyle k}$が少なくともグラフの直径である場合、${\displaystyle k}$-ウォーク正則グラフは距離正則グラフと一致する。実際、${\displaystyle k\geq 2}$グラフは最大で重複度が 1 つの固有値を持つ${\displaystyle k}$（固有値を除く）${\displaystyle d}$そして${\displaystyle -d}$、 どこ${\displaystyle d}$がグラフの次数である場合、グラフはすでに距離正則である。 ^{[ 5 ]}