自己相補グラフ

数学のグラフ理論の分野において、自己相補グラフとは、その補グラフと同型なグラフのことである。最も単純で自明でない自己相補グラフは、4頂点パスグラフと5頂点サイクルグラフである。自己相補グラフの特徴づけは知られていない。

例

すべてのペイリーグラフは自己補完的である。^[1]たとえば、3 × 3のルークのグラフ(次数 9 のペイリーグラフ) は、中心の頂点はそのままにして、グリッドの 4 つの辺の中点と 4 つの角の役割を交換する対称性によって自己補完的である。^[2] 37 個未満の頂点を持つすべての強正則自己補完グラフはペイリーグラフである。ただし、37、41、49 個の頂点を持つ強正則グラフでもペイリーグラフではないものがある。^[3]

ラドーグラフは無限自己補数グラフである。^[4]

プロパティ

n $頂点$ の自己相補グラフは、完全グラフのちょうど半分の数、つまり $n (n - 1)/4 の$ 辺を持ち、（頂点が複数ある場合）直径は2 か 3でなければなりません。 ^[1] $n (n - 1)$ は 4 で割り切れるので、 $n は4 を法として 0 または 1 と$ 合同でなければなりません。たとえば、6 頂点のグラフは自己相補的ではありません。

計算の複雑さ

2つの自己相補グラフが同型であるかどうかを確認する問題と、与えられたグラフが自己相補的であるかどうかを確認する問題は、一般的なグラフ同型性問題と多項式時間で同等である。^[5]

参考文献

^ ab Sachs、Horst (1962)、「Über selbstkomplementäre Graphen」、Publications Mathematicae Debrecen、9 : 270–288、MR 0151953。
^ Shpectorov, S. (1998)、「相補的l ₁グラフ」、離散数学、192 (1–3): 323–331、doi :10.1016/S0012-365X(98)0007X-1、MR 1656740。
^ Rosenberg, IG (1982)、「正則および強正則自己相補グラフ」、組合せ論の理論と実践、North-Holland Math. Stud.、第60巻、アムステルダム：North-Holland、pp. 223–238、MR 0806985。
^ キャメロン、ピーター J. (1997)、「ランダムグラフ」、ポール・エルデシュの数学 II、アルゴリズムコンビネン、第 14 巻、ベルリン: シュプリンガー、pp. 333–351、arXiv : 1301.7544、Bibcode :2013arXiv1301.7544C、MR 1425227特に命題5を参照。
^ コルボーン、マーリーン J.;コルボーン、チャールズ J. (1978)、「グラフ同型性と自己相補グラフ」、SIGACT News、10 (1): 25–29、doi :10.1145/1008605.1008608。

外部リンク

ワイスシュタイン、エリック W.、「自己相補グラフ」、MathWorld

[sachs-1] Sachs、Horst (1962)、「Über selbstkomplementäre Graphen」、Publications Mathematicae Debrecen、9 : 270–288、MR 0151953。

[2] Shpectorov, S. (1998)、「相補的l ₁グラフ」、離散数学、192 (1–3): 323–331、doi :10.1016/S0012-365X(98)0007X-1、MR 1656740。

[3] Rosenberg, IG (1982)、「正則および強正則自己相補グラフ」、組合せ論の理論と実践、North-Holland Math. Stud.、第60巻、アムステルダム：North-Holland、pp. 223–238、MR 0806985。

[4] キャメロン、ピーター J. (1997)、「ランダムグラフ」、ポール・エルデシュの数学 II、アルゴリズムコンビネン、第 14 巻、ベルリン: シュプリンガー、pp. 333–351、arXiv : 1301.7544、Bibcode :2013arXiv1301.7544C、MR 1425227特に命題5を参照。

[5] コルボーン、マーリーン J.;コルボーン、チャールズ J. (1978)、「グラフ同型性と自己相補グラフ」、SIGACT News、10 (1): 25–29、doi :10.1145/1008605.1008608。