グラフの直径と支配集合

グラフの頂点$v$の隣接点集合を$N(v)$とし, $S\subseteq V$に対して $N(S)=\bigcup_{s\in S} N(s)$ と定めます. グラフ$G=(V,E)$の頂点部分集合 $D\subseteq V$ は, $D\cup N(D)=V$ となるとき支配集合 (dominating set) であると言います. 言い換えると, 任意の$v\in V\setminus D$は$D$の何らかの頂点に隣接しているとき, $D$は支配集合となります.

グラフ$G$が入力として与えられたとき, $G$がサイズ$k$の支配集合を持つかどうかを判定する問題は($k$も入力で与えられるとき)NP-完全となり, $k$をパラメタとみなしたときはW[2]-困難となります. 全探索だと $O(n^{k+1})$時間で解けますが, $k=2$の時は$O(n^\omega)$時間で解けます ($\omega\leq 2.373$は行列積の計算時間の指数).

グラフ$G$がサイズ2以下の支配集合を持たないと仮定しましょう. すると, 任意の二頂点$v_1,v_2\in V$に対して, $v_1$と$v_2$のどちらとも隣接しない頂点$w\in V\setminus \{v_1,v_2\}$ が存在することになります. では, $G$の補グラフ $\bar{G}$ を考えてみましょう. すると前述の条件は, 任意の$v_1,v_2\in V$に対してある$w\in V\setminus \{v_1,v_2\}$が存在して$w$は$v_1$と$v_2$のどちらとも隣接している, というものになります. 言い換えると任意の二頂点間には長さ2のパスがあるということを意味するため, 直径が2以下である, ということになります. したがって補グラフの直径が2以下かどうかを判定すればよく, これは隣接行列の二乗を計算すれば終わるので$O(n^{\omega})$時間で判定できるわけです. 逆に, $G$の直径が$2$以下の場合はその補グラフがサイズ$2$以下の支配集合を持たないことも言えます. この観察をまとめると,

$G$はサイズ$2$以下の支配集合を持たない iff 補グラフ$\bar{G}$の直径は2以下.

この記事の本質的な部分は以上となるのですが, 折角なのでこの事実を使って次の定理を証明しようと思います.

定理1.
任意の$d\geq 3$に対して, $d^2$頂点を持つ$(d^2-d-1)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
背理法で示します. $d^2$頂点の$(d^2-d-1)$-正則グラフでサイズ$2$以下の支配集合を持たないものが存在すると仮定し, そのグラフを$G$とします. $G$の補グラフ$\bar{G}$は $d^2$頂点を持つ$d$-正則グラフとなり, 上記の事実により$\bar{G}$の直径は$2$となります (直径=1 iff 完全グラフなので, 直径=2になる).

ところが, $d$-正則グラフで頂点数=$d^2$かつ直径=2となるものは長さ4の閉路以外に存在しない[1]ため, $d\geq 3$に矛盾 (証明終).

文献[1]の結果の証明はこちらの記事のように, 隣接行列の固有値の多重度などを考えれば得られます. 文献[1]のページ数は4ページしかなく読むのにそれほど時間がかからないと思うので興味のある方はぜひ読んでみてください.

定理2. 
任意の$d\not\in\{2,3,7,57\}$に対して, 任意の$d^2+1$頂点 $(d^2-d)$-正則グラフはサイズ$2$の支配集合を持つ.

証明.
定理1の証明とほぼ同じです. $d^2+1$頂点, $(d^2-d)$-正則でかつサイズ$2$の支配集合を持たないグラフ$G$が存在するならば, その補グラフ $\bar{G}$は$d^2+1$頂点$d$-正則グラフでしかも直径=2となります. このようなグラフは Moore graph 以外に存在しないので, $d\in \{2,3,7,57\}$ となるので矛盾です (証明終).


[1] P. Erdős, S. Fajtlowicz, A. J. Hoffman. Maximum degree in graphs of diameter 2, Networks, Vol. 10, Issue. 1, 1980.