symmetry of Kauts digraph

質問

ここが適切な場所か分からないのですが・・・。

　Kautz digraphは、対称グラフなのでしょうか。K(d, k)として、d=2のときはそのような気がしますが、自信が持てません。また、d>3のときについてはカイモク見当もつきません。

　どなたかご存知の方、ご教授頂ければ幸いです。

回答No.1

stomachman

先ず用語の確認からです。
●「Kautz digraph」
Kautz digraph, あるいはdirected Kautz graphのことですね。（Kautsじゃないです。）
K(d,k)は以下のように定義されているとして良いでしょうか？
まず(d+1)個の要素を持つ文字の集合（アルファベット)Aが決まっている。そして、この文字k個を連ねて語xを作る。すなわちx=<x[1],x[2],....,x[k]> (x[j]∈A, j=1,2,...,k)　ただし、この語の中に同じ文字が２文字続く所があってはいけない。このような条件を満たす語の集合をNとすると、その個数は|N|=(d+1)(d^k)である。
　この|N|個の語をノード（バーテックス）とする有向グラフを考える。どのノードx=<x[1],x[2],....,x[k]>についても、<x[2],x[3],....,x[k],c>である全てのノード（もちろんc∈A, c≠x[k]）へアーク（エッジ、辺）が繋がっている。（その他にはアークはない。）

●「対称グラフ」
どのアークについても、ノードxからノードyへのアークがあるならば、必ずノードyからノードxへのアークがある。（つまり無向グラフである。）

　こういう意味で宜しいでしょうか。だとしますと、答はもう自明でしょう。
d=2, k=2の場合を考えてみると<01>,<10>,<12>は確かにK(2,2)のノードである。で、<01>←→<10>ですが、<01>→<12>に関しては<12>から<01>へのアークはない。だから対称になりません。

　ではd=1の場合を考えてみますと、kが偶数のときノードは<010...1>,<101...0>の２つしかない。kが奇数のときは<010...0>,<101..1>の２つしかない。いずれも対称グラフになります。

◎どうもご質問における「対称」の意味が、この回答とは微妙に違っているようにしか思えません。（余りに自明だもん。）お考えになっている「対称」を定義していただけませんでしょうか。

補足

stomachmanさん、回答ありがとうございます。

　回答を見せて頂いてから気付いたのですが、私が知りたいのは対称かどうかではなく、再帰構造をしているか(あるサイズのKautz digraphを、更に小さいサイズのいくつかのKautz digraphに分解できるか)でした。すいません。お詫びして訂正します。

　ところで、「対称」の定義についてですが、stomachmanさんのと私のとではかなり違うようです。私の中では、「対称」とは、平たく書けば、「どの頂点から見てもグラフが同じように見える」ということです(堅く書けば、グラフの任意の二頂点i, jに対して、iからjへの自己同型写像が存在するということです)。ちなみに、Kautzと並べられることの多いde Bruijnは対称ではなく、再帰構造もしていません。hypercubeは対称ですし、再帰構造をしています。また、rotator graphは有向グラフですが、対称で再帰構造をしています(と私は認識しています)。