循環グラフ

グラフ理論において、巡回グラフは、任意の頂点を他の任意の頂点に移動させる対称性の巡回群によって作用される無向グラフである。巡回グラフと呼ばれることもあるが^[1]、この用語には他の意味もある。

循環グラフはいくつかの同等の方法で記述できる: ^[2]

• グラフの自己同型群には、グラフの頂点に推移的に作用する巡回部分群が含まれます。言い換えると、グラフ には、頂点の巡回順列である自己同型があります。
• グラフには、循環行列である隣接行列があります。
• グラフの n 個の頂点には 0 から n − 1 までの番号が付けられ、番号xと( x + d ) mod n が付けられた 2 つの頂点が隣接している場合、番号 zと (  z +  d ) mod nが 付け られた すべての 2 つの頂点が隣接しています。
• グラフは、その頂点が正多角形の角に位置するように（交差を含めて）描くことができ、多角形のすべての回転対称性は、描画の対称性でもある。
• グラフは巡回群のケーリーグラフである。^[3]

すべてのサイクル グラフは循環グラフであり、頂点の数が 4 を法として 2 に一致する すべてのクラウン グラフも同様です。

n次( nは4 を法として 1と合同な素数)のPaleyグラフは、頂点が 0 からn − 1までの数であり、2 つの頂点の差がn を法 として平方剰余である場合にそれらの頂点は隣接しているグラフです。辺の有無は 2 つの頂点数のn を法として差のみに依存するため 、任意の Paley グラフは循環グラフです。

すべてのメビウスの梯子は循環グラフであり、すべての完全グラフも同様です。完全二部グラフは、その二分グラフの両側に同じ数の頂点がある場合に循環グラフになります。

2 つの数mとnが互いに素である場合、m × n ルークのグラフ( m × n チェス盤の各マスに頂点があり、ルークが1 回の移動で移動できる2 つのマスに辺があるグラフ) は巡回グラフになります。これは、その対称性に巡回群C _mn  C _m × C _{n が}サブグループとして含まれるためです。より一般的には、この場合、任意のm頂点とn頂点の巡回グラフ間のテンソル積は、それ自体が巡回グラフです。^[2]${\displaystyle \simeq}$ 

ラムゼー数の既知の下限値の多くは、最大クリークと最大独立集合が小さい循環グラフの例から来ています。^[1]

ジャンプ付き循環グラフは、各ノードiが 2 k 個のノードに隣接するラベルの付いたノードを持つグラフとして定義されます。 ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$${\displaystyle s_{1},\ldots ,s_{k}}$${\displaystyle n}$${\displaystyle 0,1,\ldots ,n-1}$${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k}\mod n}$

• グラフが連結されている場合、かつその場合のみ。${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$${\displaystyle \gcd(n,s_{1},\ldots ,s_{k})=1}$
• が固定された整数である場合、 の全域木の数は、の順序の再帰関係を満たします。 ${\displaystyle 1\leq s_{1} <\cdots <s_{k}}$ ${\displaystyle t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}}$${\displaystyle a_{n}}$${\displaystyle 2^{s_{k}-1}}$
  • 特に、はn番目のフィボナッチ数です。${\displaystyle t(C_{n}^{1,2})=nF_{n}^{2}}$${\displaystyle F_{n}}$

自己補数グラフとは、すべての辺を非辺に置き換え、またその逆を行うことで同型グラフが生成されるグラフである。例えば、5頂点の閉路グラフは自己補数であり、巡回グラフでもある。より一般的には、素数位数のペイリーグラフはすべて自己補数巡回グラフである。^[4] ホルスト・ザックスは、数nがnのすべての素因数が4を法として1と合同であるという性質を持つ場合、 n頂点を持つ自己補数巡回グラフが存在することを示した。彼は、この条件も必要であると予想した。つまり、 nの他の値では自己補数巡回グラフは存在できないということである。^{[2] [4]}この予想は約40年後にヴィルフレッドによって証明された。^[2]

巡回グラフの巡回番号付けを、グラフの頂点に 0 からn − 1までの番号を付けるラベル付けと定義します。つまり、番号xとyの 2 つの頂点が隣接している場合、番号zと( z − x + y ) mod nのすべての 2 つの頂点が隣接していることになります。同様に、巡回番号付けは、グラフの隣接行列が巡回行列である頂点の番号付けです。

a をnと互いに素な整数とし、b を任意の整数とする。このとき、数x をax + bに変換する線型関数は、巡回番号を別の巡回番号に変換します。András Ádám は、これらの線型写像が、巡回グラフの番号を付け直しながら巡回特性を保存する唯一の方法であると予想しました。つまり、GとH が異なる番号付けを持つ同型巡回グラフである場合、 Gの番号付けをHの番号付けに変換する線型写像が存在するということです。しかし、現在では Ádám の予想は誤りであることがわかっています。反例として、それぞれ16 個の頂点を持つグラフGとHが挙げられます。Gの頂点xは6つの近傍点x ± 1、x ± 2、x ± 7と16を法として連結されているが、Hの6つの近傍点はx ± 2、x ± 3、x ± 5と16を法として連結されている。これら2つのグラフは同型であるが、その同型性は線型写像では実現できない。^[2]

トイダの予想は、アダムの予想を、隣接するグラフの頂点間の差がすべて頂点の数と互いに素である特殊な循環グラフのクラスのみを考慮して洗練させたものである。この洗練された予想によれば、これらの特殊な循環グラフは、そのすべての対称性がn を法とする基になる加法群の対称性から生じるという性質を持つはずである。これは 2001 年と 2002 年に 2 つのグループによって証明された。^{[5] [6]}

巡回グラフには多項式時間認識アルゴリズムがあり、巡回グラフの同型性問題は多項式時間で解くことができる。^{[7] [8]}

• Weisstein、Eric W.「循環グラフ」。MathWorld。