よくカバーされたグラフ

グラフ理論において、十分に被覆されたグラフとは、最小の頂点被覆がすべて同じサイズである無向グラフのことです。ここで、頂点被覆とは、すべての辺に接する頂点の集合であり、頂点を 1 つ削除すると被覆されていない辺が残る場合に最小となります。同様に、十分に被覆されたグラフとは、すべての最大独立集合のサイズが等しいグラフです。十分に被覆されたグラフは、 1970 年に Michael D. Plummerによって定義され、初めて研究されました。

十分に被覆されたグラフには、すべての完全グラフ、バランスのとれた完全な二部グラフ、および頂点がチェス盤のマス目を表し、辺がチェスのルークの動きを表すルークのグラフが含まれます。十分に被覆された立方グラフ、十分に被覆されたクローフリーグラフ、および十分に被覆された高内周グラフの既知の特徴付けにより、これらのグラフを多項式時間で認識できますが、他の種類のグラフが十分に被覆されているかどうかをテストすることはcoNP 完全問題です。

定義

無向グラフの頂点被覆は、グラフ内のすべての辺に接する頂点の集合である。頂点被覆は、頂点を除去すると被覆特性が破壊される場合、つまり除去すると一部の辺が被覆されなくなる場合、最小である。頂点被覆が最小であるのは、それより少ない頂点数を持つ頂点被覆が他に存在しない場合である。十分に被覆されたグラフとは、すべての最小被覆も最小であるグラフである。十分に被覆されたグラフを定義した最初の論文で、プラマーは、これはすべての 2 つの最小被覆が互いに同じ数の頂点を持つという特性と「明らかに同等」であると書いている。^[1]

グラフ内の独立集合とは、どの頂点も隣接していない集合のことである。グラフ $G内の頂点被覆が$ $C$ であれば、 $C$ の補集合は独立集合でなければならない。逆もまた同様である。 $C$ が最小頂点被覆となるのは、その補集合 $I が$ 最大独立集合である場合に限る。また、 $C が$ 最小頂点被覆となるのは、その補集合が最大独立集合である場合に限る。したがって、十分に被覆されたグラフとは、すべての最大独立集合が同じサイズであるグラフ、またはすべての最大独立集合が最大であるグラフと同義である。^[2]

良く覆われたグラフを定義した最初の論文では、これらの定義は連結グラフに限定されていましたが^[3]、連結されていないグラフにも意味があります。後代の著者の中には、連結要件を、良く覆われたグラフには孤立した頂点があってはならないというより弱い要件に置き換えた人もいます^[4] 。連結された良く覆われたグラフと孤立した頂点のない良く覆われたグラフの両方について、すべての最小頂点カバーに属する必須頂点、つまり頂点は存在しません。さらに、すべての良く覆われたグラフは、すべての頂点 $vについて、グラフから$ $v を$ 削除すると最小頂点カバーがより小さいグラフが生成されるという意味で、頂点カバーの臨界グラフです^{[3] 。}

グラフ $G$ の独立複体とは、 $G$ 内の各独立集合に対して単体を持つ単体複体である。単体複体は、その最大単体がすべて同じ濃度を持つ場合、純粋であると言われ、したがって、十分に被覆されたグラフは、純粋独立複体を持つグラフと同義である。^[5]

例

チェス盤上に 8 つのルークを非攻撃的に配置します。チェス盤上に 8 つ未満のルークを非攻撃的に配置した場合、攻撃しないままの 8 つのルークまで拡張できます。

長さ 4 または 5 のサイクルグラフは十分にカバーされています。つまり、いずれの場合も、すべての最大独立集合のサイズは 2 です。長さ 7 のサイクルと長さ 3 のパスも十分にカバーされています。^[6]すべての完全グラフは十分にカバーされています。つまり、すべての最大独立集合は 1 つの頂点で構成されます。同様に、すべてのクラスターグラフ(完全グラフの互いに素な和) も十分にカバーされています。^[7]完全二部グラフは、その二分割の両側に等しい数の頂点がある場合に十分にカバーされています。これは、これらが唯一の 2 つの最大独立集合だからです。孤立した頂点のない三角形のないグラフの補グラフは十分にカバーされています。つまり、2 より大きい独立集合はなく、すべての単一の頂点は 2 頂点の独立集合に拡張できます。^[6]

ルークのグラフは十分にカバーされています。つまり、チェス盤上にルークの任意のセットを配置し、2 つのルークが互いに攻撃しないようにすると、チェス盤のすべての行と列に 1 つずつルークを配置するまで、攻撃しないルークをさらに配置し続けることが常に可能です。^[8]頂点が単純な多角形の対角線であり、辺が互いに交差する対角線のペアを接続するグラフは、その最大の独立集合が多角形の三角形分割であり、すべての三角形分割が同じ数の辺を持つため、十分にカバーされています。^[9]

$G が任意の$ $n$ 頂点グラフである場合、 Gと1 辺グラフ (つまり、 G に n 個の新しい頂点を追加して形成されるグラフ H。各頂点は次数 1 で、各頂点は G 内の異なる頂点に隣接しています) との根付き積は十分に覆われています。なぜなら $、$ $H$ 内 $の$ 最大 $独立$ $集合$ は、 $G$ $内$ の任意の独立集合と、その補集合の次数 1 の隣接点から構成される必要があり、したがってサイズが $n$ でなければならないからです。^[10]より一般的には、任意のグラフ $G$ とクリーク被覆( $G$ の頂点 $p$ をクリークに分割) が与えられている場合、各クリークに別の頂点を追加して形成されるグラフ $G$ $p は$ 十分に覆われています。根付き積は、 $p が$ $n$ 個の1 頂点クリークで構成される場合のこの構成の特殊なケースです。 ^[11]したがって、すべてのグラフは十分に覆われたグラフの誘導サブグラフです。

二部性、非常によく覆われたグラフ、そして内周

Favaron (1982) は、非常によく覆われたグラフを、各最大独立集合 (したがって各最小頂点被覆) がちょうど半分の頂点を含むよく覆われたグラフ (切断されている可能性はあるが孤立した頂点はない) と定義しています。この定義には、グラフ $G$ と 1 辺グラフの根付き積が含まれます。また、たとえば、Ravindra (1977) と Berge (1981) が研究した 2 部よく覆われたグラフも含まれます。孤立した頂点のない 2 部グラフでは、任意の 2 分割の両側が最大独立集合 (および最小頂点被覆) を形成するため、グラフがよく覆われている場合は、両側に同じ数の頂点がある必要があります。孤立した頂点のない $n$ 個の頂点を持つよく覆われたグラフでは、最大独立集合のサイズは最大で $n /2$ であるため、非常によく覆われたグラフは、最大独立集合のサイズが可能な限り大きいよく覆われたグラフです。^[12]

二部グラフ $G$ が十分に被覆されているためには、 M 内のすべての辺 uv に対して、 u と v の隣接辺の誘導部分グラフが完全な二部グラフを形成するという性質を持つ $完全$ マッチングM $が$ 存在 $する$ 必要 $が$ ある。[ 13 ] $マッチング$ に関する^特徴付けは、二部グラフから非常によく被覆されたグラフに拡張できる。グラフ $G が$ 非常によく被覆されているためには、次の 2 つの性質を持つ完全マッチング $M が存在する必要がある。$

$M$ の辺は $G$ の三角形に属しておらず、
$M$ のエッジが $G$ の 3 エッジパスの中央のエッジである場合、パスの 2 つの端点は隣接している必要があります。

さらに、 $Gが非常によく覆われている場合、$ $G$ 内のあらゆる完全マッチングはこれらの性質を満たします。^[14]

木は二部グラフの特殊なケースであり、木が十分に覆われているかどうかをテストすることは、十分に覆われた二部グラフの特徴付けのより単純な特殊なケースとして扱うことができます。つまり、 $G が$ 2 つ以上の頂点を持つ木である場合、木の葉以外の各ノードがちょうど 1 つの葉に隣接している場合にのみ、木は十分に覆われています。^[13]同じ特徴付けは、すべての頂点の低直径近傍が非巡回であるという意味で、局所的に木のようなグラフに適用されます。つまり、グラフの内周が8 以上の場合 (つまり、すべての頂点 $vについて、$ $v$ から距離 3 以内の頂点の部分グラフが非巡回である場合)、次数が 1 より大きいすべての頂点がちょうど 1 つの次数 1 の隣接頂点を持つ場合にのみ、グラフは十分に覆われています。 ^[15]密接に関連しているがより複雑な特徴付けは、内周が 5 以上の十分に覆われたグラフに適用されます。^[16]

規則性と平面性

立方体（3-正則）の十分に被覆されたグラフは分類されており、7つの3-連結例と、連結性の低い3つの無限立方体グラフ族から構成されています。^[17]

3連結立方体の十分に被覆されたグラフは7つあり、完全グラフ $K 4$ 、三角柱と五角柱のグラフ、デューラーグラフ、ユーティリティグラフ $K 3,3$ 、ユーティリティグラフからY-Δ変換によって得られる8頂点のグラフ、および14頂点の一般化ピーターセングラフ $G (7,2)$ である。^[18]これらのグラフのうち、最初の4つは平面グラフである。これらは、十分に被覆された4つの立方多面体グラフ（単純な凸多面体のグラフ）である。 ^[19] 4つのグラフ（2つの柱、デューラーグラフ、および $G (7,2)$ ）は一般化ピーターセングラフである。

1 頂点接続および 2 頂点接続の立方体ウェルカバーグラフはすべて、パスまたはサイクルのノードを、Plummer (1993) が $A$ 、 $B$ 、 $C$ と名付けた 3 つのグラフのフラグメントに置き換えることによって形成されます。フラグメント $A$ または $B は$ 、サイクルのノードまたはパスの内部ノードを置き換えるために使用できますが、フラグメント $C$ は、パスの 2 つの終了ノードを置き換えるために使用されます。フラグメント $Aには$ ブリッジが含まれているため、パスに対してこの置き換えプロセスを実行し、フラグメント $A を$ 使用してパスノードの一部を置き換え (残りのノードには他の 2 つのフラグメントを使用) ると、1 頂点接続の立方体ウェルカバーグラフが得られます。すべての 1 頂点接続の立方体ウェルカバーグラフはこの形式を持ち、このようなグラフはすべて平面です。^[17]

2頂点連結立方体グラフには2種類ある。1つはサイクルのノードをフラグメント $A$ と $B$ に置き換えて形成され、フラグメントの少なくとも2つはタイプ $Aである。このタイプのグラフが平面グラフとなるのは、タイプ$ $B$ のフラグメントを含まない場合のみである。もう1つのファミリはパスのノードをタイプ $B$ と $C$ のフラグメントに置き換えて形成され、このようなグラフはすべて平面グラフである。^[17]

3次元におけるよく覆われた単純多面体の特徴付けを補完するために、研究者らはよく覆われた単体多面体、または同等のよく覆われた最大平面グラフも検討した。5つ以上の頂点を持つすべての最大平面グラフは、頂点の接続性が3、4、または5である。^[20]よく覆われた5接続最大平面グラフは存在せず、4接続でよく覆われた最大平面グラフは、正八面体、五角形二錐、スナブ二蝶形、および12頂点、30辺、20三角形の面を持つ不規則多面体（非凸三角錐）のグラフの4つだけ存在する。しかし、3接続でよく覆われた最大平面グラフは無限に存在する。^[21]例えば、 $3 t$ 頂点の最大平面グラフが $t 個の$ 互いに交わらない三角形面を持つ場合、これらの面はクリーク被覆を形成する。したがって、これらのグラフに対してクリーク被覆を構成すると、t 個の $三角形$ のそれぞれを中央の頂点で交わる 3 つの新しい三角形に分割し、十分に被覆された最大平面グラフが生成される。^[22]

複雑

グラフに異なるサイズの2つの最大独立集合が含まれているかどうかをテストすることはNP完全です。つまり、相補的に、グラフが十分にカバーされているかどうかをテストすることはcoNP完全です。^[23]十分にカバーされていることがわかっているグラフで最大独立集合を見つけることは簡単ですが、すべてのグラフで最大独立集合または入力が十分にカバーされていないという保証のいずれかを出力として生成するアルゴリズムもNP困難です。^[24]

対照的に、与えられたグラフ $Gが非常によく覆われているかどうかを$ 多項式時間でテストすることが可能です。そのためには、非常によく覆われたグラフ内の一致したエッジの 2 つの特性を満たすエッジで構成される $G$ のサブグラフ $H を見つけ、次にマッチングアルゴリズムを使用して$ $H が$ 完全マッチングを持つかどうかをテストします。^[14]ハミルトン閉路を見つける問題など、任意のグラフに対して NP 完全な問題も、非常によく覆われたグラフでは多項式時間で解決できます。^[25]

すべての最大マッチングが最大である場合、グラフは等マッチング可能であると言われます。つまり、その線グラフが十分にカバーされている場合、グラフは等マッチング可能です。 ^[26]すべての最大マッチングが完全マッチングである場合、より強くランダムマッチング可能と呼ばれます。連結されたランダムマッチング可能なグラフは、完全グラフとバランスの取れた完全二部グラフのみです。^{[27]線グラフ、またはより一般的には}クローフリーグラフが十分にカバーされているかどうかを多項式時間でテストできます。^[28]

内周が5以上のよく覆われたグラフと3正則なよく覆われたグラフの特徴づけは、これらのグラフを認識するための効率的な多項式時間アルゴリズムにもつながります。^[29]

注記

^ Plummer (1970)。Plummer はグラフの頂点を意味するのに「点」を、辺を意味するのに「線」を、頂点被覆を意味するのに「点被覆」を使用していますが、この用語は使われなくなっています。
^ プラマー（1993年）。
^ ab プラマー（1970）。
^ ファヴァロン（1982年）。
^ この用語を使用している論文の例については、Dochtermann & Engström (2009) および Cook & Nagel (2010) を参照してください。
^ ab Sankaranarayana (1994)、セクション2.4、「例」、p. 7。
^ ホロイド＆タルボット（2005年）。
^ ルークのグラフは、完全な二部グラフの線グラフと同義であるため、ルークのグラフの well-covered プロパティは、完全な二部グラフが等マッチング可能であるという事実と同義です。これについては、Sumner (1979) および Lesk、Plummer、Pulleyblank (1984) を参照してください。
^ グリーンバーグ（1993年）。
^ このクラスの例は Fink ら (1985) によって研究されました。これらは (同じく十分被覆されている 4 辺サイクルとともに) まさに支配数が $n /2$ であるグラフです。その十分被覆特性は Dochtermann & Engström (2009) の定理 4.4 のように別の用語 (純粋独立複体を持つ) でも述べられています。
^ クリーク被覆の構築については、Cook & Nagel (2010)、補題 3.2 を参照してください。この情報源では、独立複体の純度の観点から結果を述べており、ルート付き積の特殊なケースに対して「完全にウィスカー化された」という用語を使用しています。
^ ベルゲ（1981年）。
^ ab ラビンドラ (1977);プラマー (1993)。
^ ab Staples (1975); Favaron (1982); Plummer (1993)。
^ Finbow & Hartnell (1983); Plummer (1993)、定理4.1。
^ Finbow & Hartnell (1983); Plummer (1993)、定理4.2。
^ abc Campbell (1987); Campbell & Plummer (1988); Plummer (1993).
^ Campbell (1987); Finbow、Hartnell、Nowakowski (1988); Campbell、Ellingham、Royle (1993); Plummer (1993).
^ キャンベル＆プラマー（1988年）。
^ 1、2、3、4 頂点の完全グラフはすべて最大平面グラフであり、十分に被覆されています。これらのグラフの頂点の接続性は、より大きな最大平面グラフには関係のない頂点の接続性の定義の詳細に応じて、無制限または最大 3 のいずれかになります。
^ Finbow、Hartnell、Nowakowski et al. (2003、2009、2010)。
^ このようにして構築されたグラフは、Finbow ら (2016) によって - ファミリーと呼ばれています。追加の例は、より小さなグラフを結合するための O 結合と呼ばれる操作によって構築できます。 $K_{4}$
^ サンカラナラーヤナ & スチュワート (1992);フヴァータルとスレーター (1993);カロ、セブジ、タルシ (1996)。
^ ラガヴァン＆スピンラッド（2003年）。
^ サンカラナラヤナ＆スチュワート（1992）。
^ レスク、プラマー、プーリーブランク（1984年）。
^ サムナー（1979年）。
^ レスク、プラマー、プーリーブランク (1984);タンカスとタルシ (1996);タンカスとタルシ (1997)。
^ キャンベル、エリンガム、ロイル（1993）；プラマー（1993）。

参考文献

ベルジュ、クロード(1981)、「正規化可能グラフ、エッジクリティカルグラフ、 $B$ グラフの共通特性」、グラフ理論とアルゴリズム (Proc. Sympos.、Res. Inst. Electr. Comm.、東北大学、仙台、1980)、Lecture Notes in Computer Science、vol. 108、ベルリン: Springer、pp. 108–123、doi : 10.1007/3-540-10704-5_10、ISBN 978-3-540-10704-0、MR 0622929。
Campbell, SR (1987)、「平面の十分に被覆されたグラフに関するいくつかの結果」、博士論文、ヴァンダービルト大学、数学科Plummer (1993) より引用。
Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993)、「十分にカバーされた立方グラフの特徴付け」、Journal of Combinatorial Mathematics and Combinatorial Computing、13 : 193–212、MR 1220613。
キャンベル、スティーブン R.;プラマー、マイケル D. (1988)、「十分に覆われた 3 次元多面体について」、Ars Combinatoria、25 (A): 215–242、MR 0942505。
カロ、ヤイール。Sebő, アンドラーシュ州; Tarsi、Michael (1996)、「貪欲な構造の認識」、Journal of Algorithms、20 (1): 137–156、doi :10.1006/jagm.1996.0006、MR 1368720。
Chvátal, Václav ; Slater, Peter J. (1993)、「十分にカバーされたグラフに関する注記」、グラフ理論のどこへ向かうのか?、Annals of Discrete Mathematics、vol. 55、アムステルダム: North-Holland、pp. 179–181、MR 1217991。
Cook, David II; Nagel, Uwe (2010)、「Cohen-Macaulay グラフとフラグ複体の面ベクトル」、SIAM Journal on Discrete Mathematics、26 : 89–101、arXiv : 1003.4447、Bibcode :2010arXiv1003.4447C、doi :10.1137/100818170。
ドクテルマン、アントン、エングストローム、アレクサンダー (2009)、「組合せトポロジーによるエッジイデアルの代数的性質」、電子組合せ論ジャーナル、16 (2): 研究論文 2、doi : 10.37236/68、MR 2515765。
ファヴァロン、O. (1982)、「非常によく覆われたグラフ」、離散数学、42 (2–3): 177–187、doi : 10.1016/0012-365X(82)90215-1、MR 0677051。
Finbow, AS; Hartnell, BL (1983)、「星による覆いに関するゲーム」、Ars Combinatoria、16 (A): 189–198、MR 0737090。
Finbow, A.; Hartnell, B.; Nowakowski, R. (1988)、「よく支配されたグラフ: よくカバーされたグラフのコレクション」、Ars Combinatoria、25 (A): 5–10、MR 0942485。
Finbow, A.; Hartnell, B.; Nowakowski, RJ (1993)、「内周 5 以上の十分に覆われたグラフの特徴付け」、Journal of Combinatorial Theory、シリーズ B、57 (1): 44–68、doi : 10.1006/jctb.1993.1005、MR 1198396。
Finbow, A.; Hartnell, B.; Nowakowski, R.; Plummer, Michael D. (2003)、「十分に被覆された三角形分割について。I」、Discrete Applied Mathematics、132 (1–3): 97–108、doi : 10.1016/S0166-218X(03)00393-7、MR 2024267。
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2009)、「十分に覆われた三角形分割について。II」、Discrete Applied Mathematics、157 (13): 2799–2817、doi : 10.1016/j.dam.2009.03.014、MR 2537505。
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2010)、「十分に覆われた三角形分割について。III」、Discrete Applied Mathematics、158 (8): 894–912、doi : 10.1016/j.dam.2009.08.002、MR 2602814。
Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2016)、「Well-covered triangulations: Part IV」、Discrete Applied Mathematics、215 : 71–94、doi : 10.1016/j.dam.2016.06.030、MR 3548980。
Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985)、「支配数がその順序の半分であるグラフについて」、Period. Math. Hungar.、16 (4): 287–293、doi :10.1007/BF01848079、MR 0833264、S2CID 121734811。
グリーンバーグ、ピーター (1993)、「区分的 $SL 2 Z$ 幾何学」、アメリカ数学会誌、335 (2): 705–720、doi :10.2307/2154401、JSTOR 2154401、MR 1140914。
Holroyd, Fred; Talbot, John (2005)、「Erdős-Ko-Rado 特性を持つグラフ」、離散数学、293 (1–3): 165–176、arXiv : math/0307073、doi :10.1016/j.disc.2004.08.028、MR 2136060。
Lesk, M.; Plummer, MD; Pulleyblank, WR (1984)、「Equi-matchable graphs」、Bollobás, Béla (ed.)、Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős、ロンドン: Academic Press、pp. 239–254、MR 0777180。
プラマー、マイケル D. (1970)、「グラフにおけるいくつかの被覆概念」、Journal of Combinatorial Theory、8 :91–98、doi : 10.1016/S0021-9800(70)80011-4、MR 0289347。
Plummer, Michael D. (1993)、「Well-covered graphs: a survey」、Quaestiones Mathematicae、16 (3): 253–287、doi :10.1080/16073606.1993.9631737、MR 1254158、2012 年 5 月 27 日のオリジナルからアーカイブ。
ラガヴァン、ヴィジェイ、スピンラッド、ジェレミー (2003)、「制限されたドメイン向けの堅牢なアルゴリズム」、アルゴリズムジャーナル、48 (1): 160–172、doi :10.1016/S0196-6774(03)00048-8、MR 2006100、S2CID 16327087。
ラビンドラ、G. (1977)、「よく覆われたグラフ」、組合せ論、情報およびシステム科学ジャーナル、2 (1): 20–21、MR 0469831。
Sankaranarayana, Ramesh S. (1994)、Well-covered graphs: some new sub-classs and complexities results (博士論文)、アルバータ大学
Sankaranarayana, Ramesh S.; Stewart, Lorna K. (1992)、「十分にカバーされたグラフの複雑性の結果」、Networks、22 (3): 247–262、CiteSeerX 10.1.1.47.9278、doi :10.1002/net.3230220304、MR 1161178。
ステープルズ、J. (1975)、十分に被覆されたグラフのいくつかのサブクラスについて、博士論文、ヴァンダービルト大学、数学部Plummer (1993) より引用。
サムナー、デイビッド P. (1979)、「ランダムにマッチ可能なグラフ」、グラフ理論ジャーナル、3 (2): 183–186、doi :10.1002/jgt.3190030209、MR 0530304。
Tankus, David; Tarsi, Michael (1996)、「Well-covered claw-free graphs」、Journal of Combinatorial Theory、シリーズ B、66 (2): 293–302、doi : 10.1006/jctb.1996.0022、MR 1376052。
Tankus, David; Tarsi, Michael (1997)、「十分にカバーされたグラフの構造とその認識問題の複雑さ」、Journal of Combinatorial Theory、シリーズ B、69 (2): 230–233、doi : 10.1006/jctb.1996.1742、MR 1438624。

[1] Plummer (1970)。Plummer はグラフの頂点を意味するのに「点」を、辺を意味するのに「線」を、頂点被覆を意味するのに「点被覆」を使用していますが、この用語は使われなくなっています。

[FOOTNOTEPlummer1993-2] プラマー（1993年）。

[FOOTNOTEPlummer1970-3] プラマー（1970）。

[FOOTNOTEFavaron1982-4] ファヴァロン（1982年）。

[5] この用語を使用している論文の例については、Dochtermann & Engström (2009) および Cook & Nagel (2010) を参照してください。

[FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7-6] Sankaranarayana (1994)、セクション2.4、「例」、p. 7。

[FOOTNOTEHolroydTalbot2005-7] ホロイド＆タルボット（2005年）。

[8] ルークのグラフは、完全な二部グラフの線グラフと同義であるため、ルークのグラフの well-covered プロパティは、完全な二部グラフが等マッチング可能であるという事実と同義です。これについては、Sumner (1979) および Lesk、Plummer、Pulleyblank (1984) を参照してください。

[FOOTNOTEGreenberg1993-9] グリーンバーグ（1993年）。

[10] このクラスの例は Fink ら (1985) によって研究されました。これらは (同じく十分被覆されている 4 辺サイクルとともに) まさに支配数が $n /2$ であるグラフです。その十分被覆特性は Dochtermann & Engström (2009) の定理 4.4 のように別の用語 (純粋独立複体を持つ) でも述べられています。

[cn10-11] クリーク被覆の構築については、Cook & Nagel (2010)、補題 3.2 を参照してください。この情報源では、独立複体の純度の観点から結果を述べており、ルート付き積の特殊なケースに対して「完全にウィスカー化された」という用語を使用しています。

[FOOTNOTEBerge1981-12] ベルゲ（1981年）。

[r77p93-13] ラビンドラ (1977);プラマー (1993)。

[sfp-14] Staples (1975); Favaron (1982); Plummer (1993)。

[15] Finbow & Hartnell (1983); Plummer (1993)、定理4.1。

[16] Finbow & Hartnell (1983); Plummer (1993)、定理4.2。

[ccpp-17] Campbell (1987); Campbell & Plummer (1988); Plummer (1993).

[18] Campbell (1987); Finbow、Hartnell、Nowakowski (1988); Campbell、Ellingham、Royle (1993); Plummer (1993).

[FOOTNOTECampbellPlummer1988-19] キャンベル＆プラマー（1988年）。

[20] 1、2、3、4 頂点の完全グラフはすべて最大平面グラフであり、十分に被覆されています。これらのグラフの頂点の接続性は、より大きな最大平面グラフには関係のない頂点の接続性の定義の詳細に応じて、無制限または最大 3 のいずれかになります。

[21] Finbow、Hartnell、Nowakowski et al. (2003、2009、2010)。

[22] このようにして構築されたグラフは、Finbow ら (2016) によって - ファミリーと呼ばれています。追加の例は、より小さなグラフを結合するための O 結合と呼ばれる操作によって構築できます。 $K_{4}$

[23] サンカラナラーヤナ & スチュワート (1992);フヴァータルとスレーター (1993);カロ、セブジ、タルシ (1996)。

[24] ラガヴァン＆スピンラッド（2003年）。

[25] サンカラナラヤナ＆スチュワート（1992）。

[FOOTNOTELeskPlummerPulleyblank1984-26] レスク、プラマー、プーリーブランク（1984年）。

[FOOTNOTESumner1979-27] サムナー（1979年）。

[28] レスク、プラマー、プーリーブランク (1984);タンカスとタルシ (1996);タンカスとタルシ (1997)。

[29] キャンベル、エリンガム、ロイル（1993）；プラマー（1993）。