ハイパーグラフの折れ線グラフ

グラフ理論、特にハイパーグラフ理論において、ハイパーグラフ $Hの線グラフ$ $（L(H)$ と表記）は、頂点集合が $H$ のハイパーエッジの集合であるグラフであり、2つの頂点は、対応するハイパーエッジが $H$ 内で空でない交差を持つ場合、 $L ($ $H$ $)$ 内で隣接している。言い換えると、 $L($ $H$ $) は$ 有限集合の族の交差グラフである。これは、グラフの線グラフの一般化である。

ハイパーグラフの線グラフに関する質問は、多くの場合、グラフの線グラフに関する質問の一般化です。たとえば、すべてのエッジのサイズが $kであるハイパーグラフは、$ $k$ -均一と呼ばれます。 (2-均一ハイパーグラフはグラフです)。ハイパーグラフ理論では、ハイパーグラフが $k$ -均一であることが自然に要求されることがよくあります。すべてのグラフは、何らかのハイパーグラフの線グラフですが、固定されたエッジサイズ $kが与えられた場合、すべてのグラフが何らかの$ $k$ -均一ハイパーグラフの線グラフであるとは限りません。主な問題は、各 $k \geq 3$ について、そのようなグラフを特徴付けることです。

ハイパーグラフは、各ハイパーエッジのペアが最大で1つの頂点で交差する場合に線形です。すべてのグラフは、ハイパーグラフだけでなく、線形ハイパーグラフの線グラフでもあります。^[1]

折れ線グラフけ-一様ハイパーグラフ、け≥ 3

Beineke ^{[2] は、グラフの線グラフを 9 つの}禁制誘導部分グラフのリストで特徴付けました。(線グラフに関する記事を参照してください。) k ≥ 3の任意の k-一様ハイパーグラフの線グラフについては、禁制誘導部分グラフによる特徴付けは知られておらず、Lovász ^{[3] は、}k = 3の場合、有限リストによるそのような特徴付けは存在しないことを示しました。

クラウス^{[4]は、グラフの線グラフを}クリーク被覆の観点から特徴付けた。（線グラフを参照）。任意のk≥3に対するk一様ハイパーグラフの線グラフに対するクラウス型の世界的特徴付けは、ベルゲ^[5]によって与えられた。

折れ線グラフけ-一様線形ハイパーグラフ、け≥ 3

任意のk ≥ 3に対するk均一線形ハイパーグラフの線グラフに対する Krausz 型のグローバルな特徴付けは、 Naik、Rao、Shrikhande、および Singhi によって与えられました。 ^[6]同時に、彼らは、最小頂点次数が少なくとも 69 である線形 3 均一ハイパーグラフの禁止誘導サブグラフの有限リストを発見しました。Metelsky と Tyshkevich ^[7]および Jacobson、Kézdy、および Lehel ^{[8] は、}この境界を 19 に改善しました。最後に、Skums、Suzdal、および Tyshkevich ^{[9] は}この境界を 16 に削減しました。Metelsky と Tyshkevich ^[10]はまた、k > 3 の場合、次数にどのような下限が置かれていても、線形k均一ハイパーグラフに対してそのような有限リストは存在しないことを証明しました。

線形k一様ハイパーグラフの特徴付けを見つけることの難しさは、禁制誘導サブグラフが無限に存在するという事実による。例を挙げると、m > 0 の場合、連続するダイヤモンドが次数 2 の頂点を共有する m 個のダイヤモンドグラフのチェーンを考えます。k ≥ 3 の場合、次数 2または4 のすべての頂点にペンダントエッジを追加して、ここに示すように、Naik、Rao、Shrikhande、および Singhi ^[11]の最小禁制サブグラフのファミリの 1 つを取得します。これは、多項式認識の存在や、グラフの線グラフの Beineke の禁制誘導サブグラフの特徴付けに類似した可能性を排除するものではありません。

Gの最小次数または最小エッジ次数に関する制約の下で、様々な著者^[12]による線形k一様ハイパーグラフの線グラフに対する興味深い特徴付けがいくつかあります。Naik、Rao、Shrikhande、およびSinghi ^{[13]による少なくとも}k ³ -2 k ^{2 +1の最小エッジ次数は、Jacobson、Kézdy、およびLehel}^[14]とZverovich ^{[15]によって2}k ² -3 k +1に削減され、任意のk ≥ 3のk一様線形ハイパーグラフの線グラフを特徴付けます。

最小次数（または最小辺次数）に制約がない場合の線形k一様ハイパーグラフの線グラフ認識の複雑さは不明である。k = 3で最小次数が少なくとも19の場合、多項式時間で認識が可能である。^[16]Skums、Suzdal'、およびTyshkevich ^[17]は最小次数を10に削減した。

Naik et al.、Jacoboson et al.、Metelsky et al.、Zverovich の論文には、興味深い未解決の問題や推測が数多くあります。

分離グラフ

ハイパーグラフHの分離グラフ（ D( H )と表記）は、頂点集合がHのハイパーエッジの集合であるグラフであり、対応するハイパーエッジがHで分離している場合、2つの頂点が D( H ) で隣接している。^[18]言い換えれば、 D( H ) は L( H )の補グラフである。 D( H )のクリークは L( H )の独立集合に対応し、その逆もまた同様である。

参考文献

^ (ベルゲ 1989)
^ ベイネケ（1968）
^ ロヴァース (1977)
^ クラウス（1943）
^ ベルゲ（1989）
^ ナイクら（1980）
^ メテルスキー＆ティシュケビッチ（1997）
^ ジェイコブソン、ケズディ、レヘル (1997)
^ スカムス、スズダリ、ティシュケビッチ (2009)
^ メテルスキー＆ティシュケビッチ（1997）
^ ナイクら。 (1980)、ナイクら。 (1982)
^ ナイクら。 (1980)、ナイクら。 (1982)、ヤコブソン、ケズディ & レヘル 1997、メテルスキー & ティシュケビッチ 1997、ズベロヴィッチ 2004
^ ナイクら（1980）
^ ジェイコブソン、ケズディ、レヘル (1997)
^ ズヴェロヴィッチ（2004）
^ Jacobson、Kézdy、Lehel 1997 および Metelsky、Tyshkevich 1997
^ スカムス、スズダリ、ティシュケビッチ (2009)
^ Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

Beineke, LW (1968)、「導出グラフとダイグラフについて」、Sachs, H.ヴォス、H. Walther, H. (編)、Beitrage zur Graphentheorie、ライプツィヒ: Teubner、17–23 ページ。
ベルゲ、C. (1989)、ハイパーグラフ：有限集合の組合せ論、アムステルダム：ノースホランド、MR 1013569フランス語から翻訳されました。
Bermond, JC; Heydemann, MC; Sotteau, D. (1977)、「ハイパーグラフの線グラフ I」(PDF)、離散数学、18 (3): 235–241、doi :10.1016/0012-365X(77)90127-3、MR 0463003。

Heydemann, MC; Sotteau, D. (1976)、「ハイパーグラフの線グラフ II」、Combinatorics (Proc. Fifth Hungarian Colloq.、Keszthely、1976)、Colloq. Math. Soc. J. Bolyai、vol. 18、pp. 567–582、MR 0519291。

Krausz、J. (1943)、「ホイットニーの新人のデモ」、Mat。フィズ。ラポック、50 : 75–85、MR 0018403（ハンガリー語、フランス語の要約付き）

Lovász, L. (1977)、「問題 9」、Beiträge zur Graphentheorie und deren Anwendungen、Vorgetragen auf dem Internationalen Kolloquium in Oberhof (DDR)、p. 313。

Jacobson, MS; Kézdy, Andre E.; Lehel, Jeno (1997)、「線形ユニフォームハイパーグラフの交差グラフの認識」、Graphs and Combinatorics、13 (4): 359–367、doi :10.1007/BF03353014、MR 1485929、S2CID 9173731。

Metelsky, Yury; Tyshkevich, Regina (1997)、「線形 3 ユニフォームハイパーグラフのライングラフ」、Journal of Graph Theory、25 (4): 243–251、doi :10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K、MR 1459889。

Naik, Ranjan N.; Rao, SB; Shrikhande, SS ; Singhi, NM (1980)、「kユニフォームハイパーグラフの交差グラフ」、組み合わせ数学、最適設計とその応用 (Proc. Sympos. Combin. Math. and Optimal Design、コロラド州立大学、フォートコリンズ、コロラド州、1978)、Annals of Discrete Mathematics、第 6 巻、pp. 275–279、MR 0593539。

Naik, Ranjan N.; Rao, SB; Shrikhande, SS ; Singhi, NM (1982)、「k -uniform linear hypergraphs の交差グラフ」、European Journal of Combinatorics、3 (2): 159–172、doi : 10.1016/s0195-6698(82)80029-2、MR 0670849。

Skums, PV; Suzdal', SV; Tyshkevich, RI (2009)、「線形 3 ユニフォームハイパーグラフのエッジ交差」、離散数学、309 : 3500–3517、doi : 10.1016/j.disc.2007.12.082。

Zverovich, Igor E. (2004)、「Jacobson、Kézdy、Lehel の問題に対する解法」、Graphs and Combinatorics、20 (4): 571–577、doi :10.1007/s00373-004-0572-1、MR 2108401、S2CID 33662052。

Voloshin, Vitaly I. (2009)、グラフとハイパーグラフ理論入門、ニューヨーク：Nova Science Publishers、Inc.、MR 2514872

[1] (ベルゲ 1989)

[2] ベイネケ（1968）

[3] ロヴァース (1977)

[4] クラウス（1943）

[5] ベルゲ（1989）

[6] ナイクら（1980）

[7] メテルスキー＆ティシュケビッチ（1997）

[8] ジェイコブソン、ケズディ、レヘル (1997)

[9] スカムス、スズダリ、ティシュケビッチ (2009)

[10] メテルスキー＆ティシュケビッチ（1997）

[11] ナイクら。 (1980)、ナイクら。 (1982)

[12] ナイクら。 (1980)、ナイクら。 (1982)、ヤコブソン、ケズディ & レヘル 1997、メテルスキー & ティシュケビッチ 1997、ズベロヴィッチ 2004

[13] ナイクら（1980）

[14] ジェイコブソン、ケズディ、レヘル (1997)

[15] ズヴェロヴィッチ（2004）

[16] Jacobson、Kézdy、Lehel 1997 および Metelsky、Tyshkevich 1997

[17] スカムス、スズダリ、ティシュケビッチ (2009)

[18] Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.