爪のないグラフ

数学の一分野であるグラフ理論において、クローフリーグラフとは、誘導部分グラフとしてクローを持たないグラフのことである。

クローは、完全な二部グラフ （つまり、3 つの辺、3 つの葉、および中心の頂点で構成される星型グラフ）の別名です。クローフリー グラフとは、誘導されたサブグラフがクローではないグラフです。つまり、4 つの頂点のサブセットには、このパターンで頂点を接続する 3 つの辺以外があります。同様に、クローフリー グラフとは、任意の頂点の近傍が三角形のないグラフの補集合であるグラフです。 ${\displaystyle K_{1,3}}$

クローフリーグラフは当初、線グラフの一般化として研究され、3つの重要な発見によってさらなる研究の動機づけとなった。すなわち、偶数次のクローフリー連結グラフはすべて完全マッチングを持つという事実、クローフリーグラフの最大独立集合を見つけるための多項式時間アルゴリズムの発見、およびクローフリー完全グラフの特徴付けである。^[1]これらは、数百もの数学的研究論文といくつかの調査の対象となっている。^[1]

• 任意のグラフの線グラフ はクローフリーです。は、 のすべての辺に対して頂点を持つものとして定義されます。対応する辺が で端点を共有する場合、2 つの頂点は で隣接しています。 線グラフにはクローを含めることはできません。 の 3 つの辺、、およびがすべて別の辺と端点を共有している場合 ( 、、およびを葉として、 を内部頂点として で木を形成)、これらの辺の間には別の隣接関係が存在する必要があり、この木が誘導サブグラフになることを防止します。 これは、鳩の巣原理により、 、 、およびのうち少なくとも 2 つが の2 つの端点の 1 つを互いに共有する必要があり、したがって で隣接しているためです。 線グラフは、9 つ​​の禁制サブグラフによって特徴付けられます。^[2]クローは、これらの 9 つのグラフの中で最も単純です。 この特徴付けが、クローフリー グラフを研究する最初の動機となりました。^[1]${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle e_{1}}$${\displaystyle e_{2}}$${\displaystyle e_{3}}$${\displaystyle G}$${\displaystyle e_{4}}$${\displaystyle L(G)}$${\displaystyle e_{1}}$${\displaystyle e_{2}}$${\displaystyle e_{3}}$${\displaystyle e_{4}}$${\displaystyle e_{1}}$${\displaystyle e_{2}}$${\displaystyle e_{3}}$${\displaystyle e_{4}}$${\displaystyle L(G)}$
• 任意の三角形のないグラフの補グラフは爪のないグラフである。^[3]これらのグラフには、特別なケースとして任意の完全グラフが含まれる。
• 適切な区間グラフ、すなわち区間が他の区間を含まない区間族の交差グラフとして形成される区間グラフは、4つの適切に交差する区間が爪のパターンで交差することはないため、爪なしグラフです。 ^{[3]より一般的には、適切な}円弧グラフについても同じことが言えます。^[4]
• モーザースピンドルは、平面の彩度数の下限値を提供するために使用される 7 頂点グラフであり、爪がありません。
• いくつかの多面体と多面体のグラフはクローフリーであり、これには四面体のグラフ、より一般的には任意の単体のグラフ（完全グラフ）、八面体のグラフ、より一般的には任意の交差多面体のグラフ（完全グラフから完全マッチングを削除することによって形成されるカクテルパーティーグラフと同型）、正二十面体のグラフ、^{[5] 、および}16セルのグラフが含まれます。
• シュレーフリグラフは27頂点を持つ強正則グラフであり、クローフリーである。^[5]

頂点と辺を持つグラフがクローフリーであることを、4 組の頂点それぞれをテストしてクローを誘発するかどうかを判定することにより、時間 で簡単に検証できます。^{[6]より効率的で複雑な方法として、グラフの各頂点について、その近傍の}補グラフに三角形が含まれていないことを確認することで、グラフがクローフリーかどうかをテストできます。グラフに三角形が含まれるのは、その隣接行列の3 乗に非ゼロの対角要素が含まれる場合のみであるため、三角形の検索は、行列の乗算と同じ漸近的な時間境界で実行できます。^[7]したがって、高速行列の乗算を使用すると、このクローフリー認識アルゴリズムの合計時間は になります。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle n^{4}}$${\displaystyle n\times n}$ ${\displaystyle O(n^{3.372})}$

Kloks、Kratsch、Müller (2000) は、クローフリー グラフでは各頂点に最大で 個の隣接頂点があると指摘しています。そうでない場合、Turán の定理により、頂点の隣接頂点には三角形のないグラフの補頂点を形成するのに十分な辺が残っていないことになります。この観察により、上で概説した高速行列乗算ベースのアルゴリズムでの各近傍のチェックは、行列乗算と同じ漸近的時間制限で実行できます。または、次数がさらに低い頂点の場合は、さらに高速に実行できます。このアルゴリズムの最悪のケースは、頂点がそれぞれ 個の隣接頂点を持ち、残りの頂点の隣接頂点の数が少ない場合で、その合計時間は になります。 ${\displaystyle 2{\sqrt {m}}}$${\displaystyle 2{\sqrt {m}}\times 2{\sqrt {m}}}$${\displaystyle \オメガ ({\sqrt {m}})}$${\displaystyle \オメガ ({\sqrt {m}})}$${\displaystyle O(m^{3.372/2})=O(m^{1.686})}$

クローフリーグラフには三角形のないグラフの補集合が含まれるため、頂点上のクローフリーグラフの数は三角形のないグラフの数と少なくとも同じ速さで増加し、 の2乗で指数関数的に増加する 。 に対するノード上の連結クローフリーグラフの数は、${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=1,2,\dots ,}$

1、1、2、5、14、50、191、881、4494、26389、184749、...（OEISの配列A022562）。

グラフが切断されることが許される場合、グラフの数は更に多くなります。

1、2、4、10、26、85、302、1285、6170、...（OEISの配列A086991）。

Palmer、Read、Robinson (2002) の手法により、グラフ列挙問題 としては異例なことに、クローフリー立方グラフの数を非常に効率的にカウントすることができます。

サムナー (1974) と、独立にラス・ヴェルグナス (1975) は、頂点数が偶数であるクローフリーの連結グラフはすべて完全マッチングを持つことを証明した。^[8]つまり、グラフには、各頂点がちょうど 1 つのマッチしたエッジの端点となるようなエッジの集合が存在する。線グラフの場合のこの結果の特殊なケースは、偶数個のエッジを持つ任意のグラフで、エッジを長さ 2 のパスに分割できることを意味する。完全マッチングは、クローフリー グラフの別の特徴付けにも使用できる。クローフリー グラフは、偶数次の連結された誘導サブグラフすべてが完全マッチングを持つグラフである。^[8]

サムナーの証明は、より強力に、連結されたクローフリー グラフでは、隣接する頂点のペアを見つけることができ、その頂点を削除すると残りのグラフが連結されたままになることを示している。これを示すために、サムナーは、グラフ内で可能な限り離れている頂点のペアと を見つけ、 から可能な限り離れているの隣接点となることを選択する。彼が示すように、 も も、他のノードから への最短経路上には存在できないため、 と を削除すると残りのグラフが連結されたままになる。このようにして、一致する頂点のペアを繰り返し削除すると、特定のクローフリー グラフで完全なマッチングが形成される。 ${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$

同じ証明の考え方は、が任意の頂点、が から最大限に遠い任意の頂点、が から最大限に遠い の任意の隣接頂点である場合に、より一般的に成り立ちます。さらに、と をグラフから削除しても、からのその他の距離は変わりません。したがって、から最大限に遠いペアを見つけて削除することによってマッチングを形成するプロセスは、をルートとするグラフの幅優先探索ツリーの単一の事後順トラバーサルによって線形時間で実行できます。Chrobak、Naor、Novick (1989) は、深さ優先探索に基づく代替の線形時間アルゴリズムと、同じ問題に対する 効率的な並列アルゴリズムを提供しています。${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle w}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle u}$${\displaystyle (v,w)}$${\displaystyle u}$${\displaystyle u}$

Faudree、Flandrin、Ryjáček (1997) は、次のような関連する結果をいくつか挙げています。偶数次の - 接続 -フリーグラフは、任意の に対して完全マッチングを持つ。最大で 1 次 -1 頂点を持つ奇数次のクローフリー グラフは、奇数サイクルとマッチングに分割できる。または頂点数が偶数であるクローフリー グラフの最小次数の半分以下の に対して、グラフには- 因子がある。クローフリー グラフが- 接続されている場合、任意の- エッジ マッチングは完全マッチングに拡張できる。 ${\displaystyle (r-1)}$${\displaystyle K_{1,r}}$${\displaystyle r\geq 2}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle (2k+1)}$${\displaystyle k}$

線グラフの独立集合は、その基になるグラフのマッチング、つまり2つの端点を共有しないエッジの集合に対応します。Edmonds (1965) のブロッサムアルゴリズムは、多項式時間で任意のグラフの最大マッチングを見つけます。これは、線グラフの最大独立集合を計算することと同じです。これは、Sbihi (1980) と Minty (1980) によって、すべてのクローフリーグラフのアルゴリズムに独立に拡張されました。^[9]

どちらのアプローチも、クローフリー グラフでは、独立集合内でどの頂点も 2 つ以上の隣接頂点を持つことはできないという観察を利用しており、そのため2 つの独立集合の対称差によって次数が最大 2 のサブグラフが必ず誘導される、つまりパスとサイクルの和集合となるという観察を利用しています。特に、 が最大でない独立集合である場合、それは任意の最大独立集合から偶数サイクルといわゆる増加パスだけ異なります。増加パス とは、 にない頂点と 内の頂点の間で交互に現れる誘導パスで、両方のエンドポイントは 内に 1 つの隣接頂点のみを持ちます。 と任意の増加パスとの対称差によって独立集合が大きくなるため、タスクは、最大マッチングを見つけるアルゴリズムと同様に、増加パスが見つからなくなるまで検索することに縮小されます。 ${\displaystyle I}$${\displaystyle I}$${\displaystyle I}$${\displaystyle I}$${\displaystyle I}$

Sbihi のアルゴリズムは、 Edmonds のアルゴリズムのブロッサム収縮ステップを再現し、類似しているがより複雑なクリーク収縮ステップを追加します。Minty のアプローチは、問題インスタンスを補助線グラフに変換し、Edmonds のアルゴリズムを直接使用して増加パスを見つけることです。Nakamura & Tamura 2001 による修正後、Minty の結果は、クローフリー グラフで最大重みの独立したセットを見つけるというより一般的な問題を多項式時間で解決するためにも使用できます。これらの結果をより広いクラスのグラフに一般化することも知られています。^[9] Faenza、Oriolo & Stauffer (2011) は、新しい構造定理を示すことにより、重み付き設定でも機能する 3 次時間アルゴリズムを提供しました。

完全グラフとは、彩色数と最大クリークの大きさが等しく、この等式がすべての誘導部分グラフで維持されるグラフである。現在では、完全グラフは、誘導部分グラフとして奇数サイクルまたは奇数サイクルの補集合 (いわゆる奇数ホール) を持たないグラフとして特徴付けられることが知られている (強い完全グラフ定理)。^[10]しかし、長年にわたり、これは未解決の予想のままであり、グラフの特別なサブクラスについてのみ証明されていた。これらのサブクラスの 1 つがクローフリー グラフの族である。奇数サイクルおよび奇数ホールのないクローフリー グラフは完全であることが複数の著者によって発見された。完全クローフリー グラフは多項式時間で認識できる。完全クローフリー グラフでは、任意の頂点の近傍が2 部グラフの補集合を形成する。完全クローフリー グラフを多項式時間で色付けしたり、最大クリークを見つけたりすることができる。 ^[11]

一般に、クローフリーグラフで最大のクリークを探すのはNP困難です。^[12]グラフの最適な色付けもNP困難です。これは、（線グラフを介して）この問題がグラフの彩色指数を計算するNP困難問題を一般化しているためです。^{[6]同じ理由で、4/3よりも優れた}近似比を達成する色付けを見つけることはNP困難です。ただし、クローフリーグラフの彩色数は最大次数の半分よりも大きいため、貪欲な色付けアルゴリズムによって近似比2を実現できます。エッジリスト色付け予想の一般化では、クローフリーグラフの場合、リスト彩色数は彩色数に等しいとされています。他の種類のグラフでは、これら2つの数は大きく離れている場合があります。^[13]

クローフリーグラフはχ有界であり、つまり大きな彩色数のクローフリーグラフはすべて大きなクリークを含む。さらに強いことは、ラムゼーの定理から、大きな最大次数を持つクローフリーグラフはすべて、次数の平方根にほぼ比例するサイズの大きなクリークを含むということである。少なくとも1つの3頂点独立集合を含む連結クローフリーグラフの場合、彩色数とクリークのサイズの間により強い関係が考えられ、これらのグラフには少なくとも彩色数の半分のサイズのクリークが存在する。^[14]

すべてのクローフリー グラフが完全というわけではありませんが、クローフリー グラフは完全性に関連する別の特性も満たしています。グラフが独立な最小支配集合を持ち、同じ特性がそのすべての誘導サブグラフで成り立つ場合、そのグラフは支配完全と呼ばれます。クローフリー グラフにはこの特性があります。これを確認するために、 をクローフリー グラフの支配集合とし、 とが内の 2 つの隣接頂点であるとします。すると、 によって支配され によって支配されない頂点の集合はクリークでなければなりません (そうでない場合は はクローの中心になります)。このクリーク内のすべての頂点が の少なくとも 1 つの他の要素によってすでに支配されている場合、 は削除してより小さな独立支配集合を生成することができ、そうでない場合はをそのクリーク内の非支配頂点の 1 つで置き換えて、隣接性の少ない支配集合を生成することができます。この置き換えプロセスを繰り返すことで、最終的に よりも大きくない支配集合に到達するため、特に開始集合が最小支配集合である場合、このプロセスは同程度に小さな独立支配集合を形成します。^[15]${\displaystyle D}$${\displaystyle v}$${\displaystyle w}$${\displaystyle D}$${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle D}$${\displaystyle v}$${\displaystyle v}$${\displaystyle D}$${\displaystyle D}$

この支配完全性にもかかわらず、クローフリーグラフの最小支配集合の大きさを決定することはNP困難である。^[6]しかし、より一般的なグラフのクラスの状況とは対照的に、クローフリーグラフの最小支配集合または最小連結支配集合を見つけることは、固定パラメータで扱いやすい。つまり、グラフのサイズの多項式に支配集合サイズの指数関数を掛けたもので制限された時間で解くことができる。^[16]

Chudnovsky & Seymour (2005) は、一連の論文の概要を示し、その中で、ロバートソンとシーモアが証明したマイナー閉グラフ族のグラフ構造定理、およびチュドノフスキー、シーモアと共著者が強いパーフェクトグラフ定理を証明するために使用したパーフェクトグラフの構造理論に類似した、クローフリーグラフの構造理論を証明しています。^[10]この理論はここで詳しく説明するには複雑すぎますが、その雰囲気を伝えるには、2 つの結果を概説するだけで十分です。まず、彼らが準線グラフ(同義で、局所的に共二部グラフ) と呼ぶクローフリーグラフの特別なサブクラスについて、そのようなグラフはすべて次の 2 つの形式のいずれかを持つと述べています。

1. ファジー円区間グラフは、円上の点と円弧によって幾何学的に表現されるグラフのクラスであり、適切な円弧グラフを一般化します。
2. 多重グラフの各辺をファジー線形区間グラフに置き換えることによって構築されたグラフ。これは、多重グラフのすべての辺が頂点に置き換えられる線グラフの構築を一般化したものです。ファジー線形区間グラフは、ファジー円形区間グラフと同じ方法で構築されますが、円ではなく線上に構築されます。

Chudnovsky と Seymour は、任意の連結クローフリー グラフを次のいずれかに分類します。

1. クローフリー グラフの 6 つの特定のサブクラス。これらのうち 3 つは、線グラフ、適切な円弧グラフ、および 20 面体の誘導サブグラフです。他の 3 つには追加の定義が含まれます。
2. 小さなクローフリー グラフから 4 つの簡単な方法で形成されたグラフ。
3. 反プリズマティック グラフは、 4 つの頂点ごとに少なくとも 2 つのエッジを持つサブグラフが誘導される、クローフリー グラフとして定義される密なグラフのクラスです。

彼らの構造理論の研究の多くは、反プリズマティックグラフのさらなる分析を伴う。パラメータsrg(27,16,10,8)を持つクローフリー強正則グラフであるシュレーフリグラフは、この分析の部分で重要な役割を果たしている。この構造理論は、多面体組合せ論の新たな進歩とクローフリーグラフの彩色数の新たな境界^{[5] [17]}、およびクローフリーグラフの支配集合に対する固定パラメータで扱いやすい新しいアルゴリズム^{[18]につながった。}

• Beineke, LW (1968)、「Derived charts of digraphs」、Sachs, H.;ヴォス、H.-J.ウォルター、H.-J. (編)、Beiträge zur Graphentheorie、ライプツィヒ: Teubner、17–33 ページ。
• Chrobak, Marek; Naor, Joseph; Novick, Mark B. (1989)、「制限付き次数スパニング ツリーを使用したクローフリー グラフ上の効率的なアルゴリズムの設計」、Dehne, F.; Sack, J.-R .; Santoro, N. (編)、アルゴリズムとデータ構造: ワークショップ WADS '89、カナダ、オタワ、1989 年 8 月、議事録、Lecture Notes in Comput. Sci.、vol. 382、ベルリン: Springer、pp. 147–162、doi :10.1007/3-540-51542-9_13、hdl : 1813/6891、ISBN 978-3-540-51542-5。
• チュドノフスキー、マリア、ロバートソン、ニール、シーモア、ポール、トーマス、ロビン(2006)、「強い完全グラフ定理」(PDF)、Annals of Mathematics、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、S2CID  119151552。
• チュドノフスキー、マリア、シーモア、ポール(2005)、「クローフリー グラフの構造」(PDF)、組合せ論の調査 2005、ロンドン数学会講義ノート シリーズ、第 327 巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 153–171、MR  2187738。
• チュドノフスキー、マリア;シーモア、ポール(2008)、「クローフリー グラフ。III. 円形区間グラフ」(PDF)、Journal of Combinatorial Theory、シリーズ B、98 (4): 812–834、doi : 10.1016/j.jctb.2008.03.001、MR  2418774。
• チュドノフスキー、マリア;シーモア、ポール(2010)、「クローフリーグラフ VI. カラーリング」、Journal of Combinatorial Theory、シリーズ B、100 (6): 560–572、CiteSeerX  10.1.1.220.7715、doi : 10.1016/j.jctb.2010.04.005、MR  2718677。
• Cygan, Marek; Philip, Geevarghese; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry (2011)、「支配集合は、クローフリー グラフで固定パラメータで制御可能」、Theoretical Computer Science、412 (50): 6982–7000、arXiv : 1011.6239、doi :10.1016/j.tcs.2011.09.010、MR  2894366、S2CID  16339210。
• エドモンズ、ジャック(1965)、「道、木、花」、カナダ数学ジャーナル、17 : 449–467、doi : 10.4153/CJM-1965-045-4、MR  0177907、S2CID  18909734。
• Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2011)、「重み付き安定集合問題に対するO(n ^{3 ) アルゴリズムにつながるクローフリー グラフのアルゴリズム分解」、第 22 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録}(PDF)、SODA '11、カリフォルニア州サンフランシスコ: SIAM、pp. 630–646、doi :10.1137/1.9781611973082.49、ISBN 978-0-89871-993-2、S2CID  13353335。
• フォードリー、ラルフ; フランドリン、エヴェリン; リャチェク、ズデニェク (1997)、「クローフリーグラフ - 概観」、離散数学、164 (1–3): 87–147、doi : 10.1016/S0012-365X(96)00045-3、MR  1432221。
• ゴールドバーグ、アンドリュー V. ; カルザノフ、アレクサンダー V. (1996)、「歪対称グラフのパス問題」、コンビナトリカ、16 (3): 353–382、doi :10.1007/BF01261321、S2CID  16308467。
• グラヴィエ、シルヴァン; マフレー、フレデリック (2004)、「クローフリー完全グラフの選択数について」、離散数学、276 (1–3): 211–218、doi :10.1016/S0012-365X(03)00292-9、MR  2046636。
• Hermelin, Danny; Mnich, Matthias; van Leeuwen, Erik Jan; Woeginger, Gerhard (2011)、「星が出ているときの支配」、Automata、言語とプログラミング: 第 38 回国際コロキウム、ICALP 2011、チューリッヒ、スイス、2011 年 7 月 4 ～ 8 日、議事録、パート I、Lecture Notes in Computer Science、vol. 6755、チューリッヒ、スイス、pp. 462 ～ 473、arXiv : 1012.0012、doi :10.1007/978-3-642-22006-7_39、ISBN 978-3-642-22005-0、S2CID  3080073{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)。
• イタイ、アロン; ロデ、マイケル (1978)、「グラフ内の最小回路の検出」、SIAM Journal on Computing、7 (4): 413–423、doi :10.1137/0207033、MR  0508603。
• King, Andrew D.; Reed, Bruce A. (2015)、「クローフリーグラフ、スケルタルグラフ、およびω、Δ、χに関するより強力な予想」、Journal of Graph Theory、78 (3): 157–194、arXiv : 1212.3036、doi :10.1002/jgt.21797、S2CID  7385598。
• Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000)、「小さな誘導サブグラフの効率的な検出とカウント」、Information Processing Letters、74 (3–4): 115–121、doi :10.1016/S0020-0190(00)00047-8、MR  1761552。
• Las Vergnas, M. (1975)、「グラフのマッチングに関するメモ」、Cahiers du Centre d'Études de Recherche Opérationnelle、17 (2–3–4): 257–260、MR  0412042。
• Minty, George J. (1980)、「クローフリーグラフの頂点の最大独立集合について」、Journal of Combinatorial Theory、シリーズ B、28 (3): 284–304、doi : 10.1016/0095-8956(80)90074-X、MR  0579076。
• 中村 大進; 田村 明久 (2001)、「クローフリーグラフの最大重み付き安定集合を求めるMintyアルゴリズムの改訂」、日本オペレーションズ・リサーチ学会誌、44 (2): 194–204、doi : 10.15807/jorsj.44.194。
• Palmer, Edgar M.; Read, Ronald C.; Robinson, Robert W. (2002)、「Counting claw-free cubic graphs」(PDF)、SIAM Journal on Discrete Mathematics、16 (1): 65–73、doi :10.1137/S0895480194274777、MR  1972075。
• Poljak、Svatopluk (1974)、「グラフの安定集合と色付けに関するメモ」、Commentationes Mathematicae Universitatis Carolinae、15 : 307–309、MR  0351881。
• Sbihi、Najiba (1980)、「Algorithme de recherche d'un安定したカーディナリテ最大値ダン・アン・グラフ・サン・エトワール」、離散数学、29 (1): 53–76、doi : 10.1016/0012-365X(90)90287-R、MR  0553650。
• サムナー、デイビッド P. (1974)、「1 因子グラフ」、アメリカ数学会紀要、42 (1)、アメリカ数学会: 8–12、doi :10.2307/2039666、JSTOR  2039666、MR  0323648。

• クローフリーグラフ、グラフクラス包含に関する情報システム
• Mugan, Jonathan William; Weisstein, Eric W.、「Claw-Free Graph」、MathWorld