Mooreグラフ(Moore graph)とは、最大次数 $d\ge2$、直径 $k$ の連結グラフの頂点数の上界 $1+d\sum_{i< k}(d-1)^i$ に達するグラフで、$d$ 正則かつ内周 $2k+1$ であることと同値である。$K_{d+1}$ と奇閉路のほかに、直径 $2$ の Petersen グラフと次数 $7$ の Hoffman–Singleton グラフがある。直径 $2$ の次数は $2,3,7,57$ に限られ、直径 $3$ 以上は奇閉路だけである。次数 $57$ の存在は 2011 年の文献で未解決とされている。
Mooreグラフ(Moore graph)とは、次数の上限 $d$ と直径 $k$ を決めたとき、頂点の個数が取りうる最大値 $1+d\sum_{i=0}^{k-1}(d-1)^i$ に達する連結グラフである。これは、直径 $k$ の連結グラフについて、$d$ 正則で内周が $2k+1$ であることと同値である。$k=1$ の完全グラフ $K_{d+1}$ と、$d=2$ の奇閉路 $C_{2k+1}$ のほかには、$k=2$ の次数 $3$ の Petersenグラフ、次数 $7$ の Hoffman–Singleton グラフが知られるだけである(BH11 2011 年の版の時点)。
名前は、この上界の問題に関わった E. F. Moore にちなむ。A. J. Hoffman と R. R. Singleton は 1960 年に、直径 $2$ と $3$ の場合を 隣接行列 の固有値で調べた(HS60)。R. M. Damerell と、坂内英一・伊藤達郎(Bannai–Ito)は 1973 年に、直径 $3$ 以上は奇閉路に限ることを示した(Dam73、BI73)。同じ版の時点で残っているのは、次数 $57$、直径 $2$、頂点数 $3250$ の場合である。
この記事では、上界とその等号条件を証明し、Moore グラフの距離の行列が満たす多項式の式を導く。それを使って直径 $3$ の場合を完全に解く。直径 $2$ の次数の絞り込みは 強正則グラフ の定理「Hoffman–Singleton の定理」にある。ここでは次数 $3$ の一意性と次数 $7$ の構成を証明する。
グラフは有限の単純グラフとする。頂点の距離は最短の道の長さ、直径 は連結グラフの距離の最大値、内周 は最短の閉路の長さである。Moore の上界 を
$$
M(d,k):=1+d+d(d-1)+\dots+d(d-1)^{k-1}
$$
とおく。
$d\ge2$、$k\ge1$ とし、$G$ を最大次数が $d$ 以下で直径が $k$ の連結グラフとする。$n$ を $G$ の頂点数とすると $n\le M(d,k)$ である。次の 2 つは同値である。
頂点 $v$ から出る 後戻りしない歩道($x_{i+1}\ne x_{i-1}$ である $x_0=v,x_1,\dots,x_l$)を考える。長さ $l$ のものは高々 $d(d-1)^{l-1}$ 本なので、長さ $k$ 以下のものは高々 $M(d,k)$ 本である。直径が $k$ なので、どの頂点もある歩道の終点である(最短の道は後戻りしない)。これで $n\le M(d,k)$ である。
1 ならば 2:$n=M(d,k)$ なら、どの $v$ についても歩道はちょうど $M(d,k)$ 本で、終点は相異なる。本数が最大なので $v$ の次数は $d$ である。$v$ は任意なので $G$ は $d$ 正則である。$v$ を通る長さ $l\le 2k$ の閉路があれば、$v$ から両向きに長さ $\lceil l/2\rceil$、$\lfloor l/2\rfloor$ の歩道が同じ終点に達し、どちらも長さ $k$ 以下である。これは終点が相異なることに反する。よって内周は $2k+1$ 以上である。距離 $k$ の頂点 $x$ をとると、次数は $d\ge2$ で、距離 $k-1$ の隣接点は(歩道の終点が相異なるので)1 つだけ、距離 $k+1$ の頂点はないので、距離 $k$ の隣接点 $y$ がある。$v$ から $x$、$y$ への長さ $k$ の道と辺 $xy$ を考える。2 本の道が共有する点までの部分は、歩道の終点が相異なるので一致する。共有する最後の点が $v$ から距離 $r\ge1$ なら、長さ $2(k-r)+1\le2k-1$ の閉路ができて内周が $2k+1$ 以上であることに反する。よって 2 本の道は $v$ でだけ交わり、辺 $xy$ と合わせて長さ $2k+1$ の閉路ができる。
2 ならば 1:内周が $2k+1$ なら、$v$ から出る長さ $k$ 以下の 2 本の歩道の終点が同じだと長さ $2k$ 以下の閉路ができるので、終点は相異なる。$d$ 正則なので歩道は $M(d,k)$ 本あり、$n\ge M(d,k)$ である。上界と合わせて等号である。$\square$
prop-mg-bound の同値な条件をみたす $G$ を、次数 $d$、直径 $k$ の Moore グラフ という。
この定義は BH11 §12.7(p. 177)の上界の等号の場合である。$k=1$ なら $M(d,1)=d+1$ で、$G=K_{d+1}$ である。$d=2$ なら $M(2,k)=2k+1$ で、$G=C_{2k+1}$ である。$k=2$ なら $M(d,2)=d^2+1$ である。以下 $k=1$ と $d=2$ を 自明な場合 という。
$A$ を隣接行列とする。$0\le i\le k$ について、$A_i$ を $(u,v)$ 成分が「$u,v$ の距離が $i$ なら $1$、そうでなければ $0$」の行列とする。$A_0=I$、$A_1=A$、$\sum_iA_i=J$(すべての成分が $1$ の行列)である。多項式を
$$
F_0:=1,\quad F_1:=x,\quad F_2:=x^2-d,\quad F_{i+1}:=xF_i-(d-1)F_{i-1}\ (i\ge2),\qquad G_k:=\sum_{i=0}^kF_i
$$
で定める。
$G$ を次数 $d$、直径 $k$ の Moore グラフとする。$0\le i\le k$ で $A_i=F_i(A)$ であり、$G_k(A)=J$ である。したがって $A$ の固有値は、重複度 $1$ の $d$ と、$G_k$ の根だけである。$G_k(d)=M(d,k)$ である。
$i=0,1$ は定義である。$A^2$ の $(u,v)$ 成分は共通の隣接点の個数で、内周が $5$ 以上($k\ge2$)なら $u=v$ で $d$、距離 $2$ で $1$、それ以外で $0$ である。よって $A^2=dI+A_2$ である。
$2\le i< k$ とする。$(AA_i)_{uv}$ は、$u$ の隣接点 $w$ のうち $v$ との距離が $i$ のものの個数である。内周が $2k+1$ なので、距離 $k$ 以下の 2 頂点を結ぶ長さ $k$ 以下の道はただ 1 本である。$u$ と $v$ の距離 $e$ で場合を分ける。$e=i+1$ なら、$w$ は道の上の次の点だけなので $1$ である。$e=i-1$ なら、道の上の点以外の $d-1$ 個の隣接点が距離 $i$ である。それ以外の $e$ では $0$ である。$e=i$ で $w$ が距離 $i$ なら長さ $2i+1\le2k-1$ の閉路ができるからである。よって $AA_i=A_{i+1}+(d-1)A_{i-1}$ で、帰納法から $A_i=F_i(A)$ である。
$A$ は対称で $G$ は連結なので、固有値 $d$ の重複度は $1$ で固有ベクトルは定数である。他の固有ベクトルは定数と直交するので $J$ で $0$ になり、固有値 $\theta$ は $G_k(\theta)=0$ をみたす。定数ベクトルに $G_k(A)=J$ を当てると $G_k(d)=n=M(d,k)$ である。$\square$
低い次数では、$q:=d-1$ とおいて
$$
G_2=x^2+x-q,\qquad G_3=x^3+x^2-2qx-q
$$
である。一般に $G_0:=1$ として $G_{k+1}=xG_k-qG_{k-1}$($k\ge1$)である。$F_i$ の漸化式を $i=2,\dots,k$ で足せばよい。これは第 2 種 Chebyshev 多項式の漸化式と同じ形である。
次数 $d\ge2$ の Moore グラフの $d$ 以外の固有値 $\theta$ は、$\lvert\theta\rvert< 2\sqrt{d-1}$ をみたす実数である。
$q\ge1$、$c:=q^{-1/2}\le1$ とする。漸化式と $G_0,G_1$ の値から、$x=2\sqrt q\cos t$ とおくと
$$
G_k(x)=q^{k/2}\,\frac{h(t)}{\sin t},\qquad h(t):=\sin((k+1)t)+c\sin(kt)
$$
である。$t_j:=j\pi/(k+1)$($1\le j\le k$)では $h(t_j)=(-1)^{j+1}c\sin t_j$ で、符号が交互に変わる。$t\to\pi$ で $h(t)/\sin t\to(-1)^k(k+1-ck)$ で、$k+1-ck\ge1$ なので符号は $(-1)^k$ である。これは $h(t_k)$ の符号 $(-1)^{k+1}$ と逆である。したがって $h$ は $(t_1,\pi)$ に少なくとも $k$ 個の零点をもつ。$\cos$ は $(0,\pi)$ で単射なので、次数 $k$ の $G_k$ の根はすべてこれらから得られ、$(-2\sqrt q,2\sqrt q)$ にある。あとは thm-mg-polynomial である。$\square$
例えば Petersen グラフでは $2\sqrt2\approx2.83$ に対して固有値は $1$、$-2$ である。
$\{1,\dots,5\}$ の 2 点部分集合を頂点とし、交わらないものを結ぶ。各頂点は $\binom32=3$ 個に隣接し、頂点数は $10=M(3,2)$ である。隣接する $\{a,b\},\{c,d\}$ に共通の隣接点はない(2 点の補集合は残り 1 点しかない)。1 点だけ共有する $\{a,b\},\{a,c\}$ の共通の隣接点は、残り 2 点の組ただ 1 つである。よって長さ $3$、$4$ の閉路がなく、直径 $2$ の Moore グラフである。
直径 $2$ の Moore グラフは、隣接する 2 頂点に共通の隣接点がなく、隣接しない 2 頂点に共通の隣接点がちょうど 1 つあるグラフである。すなわち強正則グラフ $\mathrm{srg}(d^2+1,d,0,1)$ である。強正則グラフ の定理「Hoffman–Singleton の定理」により、$d\in\{2,3,7,57\}$ である。固有値は $G_2$ の 2 根で、重複度は $n-1$ の分け方と跡 $0$ から決まる。
| $d$ | 頂点数 | 固有値(重複度) | 存在 |
|---|---|---|---|
| $2$ | $5$ | $\frac{-1\pm\sqrt5}2$($2$、$2$) | $C_5$ |
| $3$ | $10$ | $1$($5$)、$-2$($4$) | Petersenグラフ |
| $7$ | $50$ | $2$($28$)、$-3$($21$) | Hoffman–Singleton グラフ |
| $57$ | $3250$ | $7$($1729$)、$-8$($1520$) | 2011 年の文献で未解決 |
$d=4$ なら $G_2=x^2+x-3$ の根は $\frac{-1\pm\sqrt{13}}2$ で無理数である。2 根は共役なので重複度は等しく、$m$ とおくと $2m=16$、跡は $4+8\cdot(-1)=-4\ne0$ となって矛盾する。一般に根が無理数なら $d=2$ に限られ、根が整数なら $4d-3$ が平方数で、重複度の整数性から $d\in\{3,7,57\}$ に絞られる。
次数 $3$、直径 $2$ の Moore グラフは同型を除いて 1 つで、Petersenグラフ である。
頂点 $v$ をとり、隣接点を $a,b,c$、それぞれの残りの隣接点を $a_1,a_2$、$b_1,b_2$、$c_1,c_2$ とする。頂点は全部で $10$ 個である。6 頂点 $a_1,\dots,c_2$ はそれぞれ残り 2 本の辺をこの 6 頂点の中にもつので、誘導部分グラフは 2 正則である。内周が $5$ なので閉路の長さは $5$ 以上で、2 正則グラフとして $6$ 閉路である。$a_1,a_2$ は隣接せず($3$ 閉路になる)、共通の隣接点をもたない($4$ 閉路になる)ので、$6$ 閉路の上で距離 $3$ である。$b$、$c$ の組も同じである。したがって $6$ 閉路 $x_0\cdots x_5$ の対蹠点の 3 組が $a,b,c$ の下の組になる。これでグラフは決まる。Petersen グラフは次数 $3$、内周 $5$、頂点数 $10$ なので、これに一致する。$\square$
次数 $7$ のグラフは Robertson の次の形に書ける(BH11 p. 117)。
頂点を $P_{h,j}$、$Q_{i,j}$($h,i,j\in\mathbb{Z}/5$)の $50$ 個とする。辺を
$$
P_{h,j}\sim P_{h,j\pm1},\qquad Q_{i,j}\sim Q_{i,j\pm2},\qquad P_{h,j}\sim Q_{i,hi+j}
$$
で定める。これは次数 $7$、直径 $2$ の Moore グラフである。
各頂点の次数は $2+5=7$ で、$M(7,2)=50$ である。長さ $3$、$4$ の閉路がないことを示せばよい。そのとき、各頂点から出る長さ $2$ 以下の後戻りしない歩道 $50$ 本の終点は相異なるので全頂点に達し、直径は $2$ となって $n=M(7,2)$ である。
$P_{h,j}$ は各 $i$ についてちょうど 1 つの $Q_{i,l}$ に隣接する。$Q_{i,l}$ は各 $h$ についてちょうど 1 つの $P_{h,l-hi}$ に隣接する。さらに次が成り立つ。
次数 $7$ のものも同型を除いて 1 つである(BH11 p. 117。この記事では証明しない)。次数 $57$ のものがあるかどうかは、BH11(2011 年の版)p. 117 の時点で分かっていない。あるとしても、ランク $3$ の自己同型群をもたず(Aschbacher)、頂点推移的でない(G. Higman)ことが BH11 §11.5.1(p. 169)に述べられている。
次数 $d\ge2$、直径 $3$ の Moore グラフは $C_7$ だけである。
$q:=d-1\ge1$ とする。$G_3=x^3+x^2-2qx-q$ は既約である。実際、有理根はモニックなので整数 $a$ で、$a^3+a^2=q(2a+1)$ である。恒等式
$$
8(a^3+a^2)=(2a+1)(4a^2+2a-1)+1
$$
より $2a+1$ は $1$ を割るので $a\in\{0,-1\}$ である。どちらも代入すると $q=0$ となり矛盾する。
$A$ は整数行列なので固有多項式は有理係数で、$G_3$ の 3 根は共役だから重複度は等しい。これを $m$ とする。thm-mg-polynomial より $d$ 以外の固有値は $G_3$ の根である。また $G_3(d)=M(d,3)\ne0$ なので $d$ は根でない。根の和は $-1$ で、$\operatorname{tr}A=0$ より $d-m=0$ である。頂点数を比べると
$$
1+3d=n=M(d,3)=1+d(1+q+q^2)
$$
なので $1+q+q^2=3$、$q=1$ である。$d=2$ で $G=C_7$ である。$\square$
この定理は HS60 の結果である。同じ考え方は次の定理へ延びる。
直径 $k\ge3$ の Moore グラフは奇閉路 $C_{2k+1}$ だけである。
これは BH11 Theorem 12.7.1(p. 178)にあり、この記事では証明しない。証明は thm-mg-diameter-three と同じく、共役な固有値の重複度が等しいという有理性の条件を使う。$k$ が大きいと $G_k$ が既約とは限らないので、その分だけ議論が難しくなる。
内周が偶数の場合には、prop-mg-bound の類似の上界の等号が一般多角形と関係する。W. Feit と G. Higman の定理によれば、$s,t>1$ の有限な一般 $m$ 角形は $m\in\{2,3,4,6,8\}$ に限られる(BH11 Theorem 12.7.2、p. 178)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 直径が $k$(prop-mg-bound の仮定。$k=2$ とみる) | 正十二面体のグラフ | 2 ならば 1($3$ 正則・内周 $5$ でも $n=M(3,2)$ でない)、上界 $n\le M(3,2)$ |
| 内周 $2k+1$(prop-mg-bound の 2) | $K_{3,3}$ | $n=M(3,2)$ であること、$G_2(A)=J$ |
| 等号($d$ 正則の結論) | 星グラフ $K_{1,3}$ | $d$ 正則であること |
| $d\ge3$($k\ge3$ の非存在) | $C_7$ | 次数 $d$、直径 $3$ の Moore グラフがないこと |
正十二面体のグラフ:$3$ 正則で内周 $5$、頂点数 $20>M(3,2)=10$ で、直径は $5$ である。直径が $2$ でないので prop-mg-bound の仮定を外れている。内周 $5$ から後戻りしない歩道の終点が相異なることは言え $n\ge M(3,2)$ は成り立つが、上界と等号は成り立たない。
$K_{3,3}$:$3$ 正則で直径 $2$ だが、内周 $4$ で頂点数 $6< 10$ である。同じ側の 2 頂点の共通の隣接点は $3$ 個なので、$A^2$ の非対角成分は $3$ になり、$A^2+A-2I=J$ でない。
$K_{1,3}$:最大次数 $3$、直径 $2$、頂点数 $4< 10$ で、$3$ 正則でない。閉路がない。
$C_7$:thm-mg-diameter-three のとおり、$d=2$ では存在するので、$k\ge3$ の非存在は $d\ge3$ でだけ言える。$\square$
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する