ハイパーグラフの折れ線グラフ
線グラフのハイパーグラフへの一般化

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

ハイパーグラフの線グラフに関する問題は、多くの場合、グラフの線グラフに関する問題の一般化です。例えば、すべての辺のサイズがkであるハイパーグラフはk -均一と呼ばれます。（2-均一ハイパーグラフはグラフです）。ハイパーグラフ理論では、ハイパーグラフがk -均一であることが自然に求められることがよくあります。すべてのグラフは何らかのハイパーグラフの線グラフですが、固定された辺サイズkが与えられた場合、すべてのグラフが何らかの k -均一ハイパーグラフの線グラフであるとは限りません。主な問題は、各k ≥ 3に対して、 k -均一ハイパーグラフの線グラフを特徴付けることです。

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

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

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

Krausz [4]は、グラフの線グラフをクリーク被覆の観点から特徴付けた。（線グラフを参照）。任意のk≥3に対するk一様ハイパーグラフの線グラフに対するKrausz型の世界的特徴付けは、 Berge [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 3 -2 k 2 +1 の最小エッジ次数は、Jacobson、Kézdy、およびLehel [14]と Zverovich [15]によって 2 k 2 -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で分離している場合、D( H )では2つの頂点が隣接している。[18]言い換えれば、D( H )はL( H )の補グラフである。D ( H )のクリークはL( H )の独立集合に対応し、その逆もまた同様である。

参考文献

  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.
  • Beineke, LW (1968)、「導出グラフとダイグラフについて」、Sachs, H.ヴォス、H. Walther , H. (編)、Beitrage zur Graphentheorie 、ライプツィヒ: Teubner、 17–23ページ 。
  • Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets , Amsterdam: North-Holland, 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), "Line graphs of hypergraphs 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 -uniform hypergraphs の交差グラフ」、組み合わせ数学、最適設計とその応用 (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。
「https://en.wikipedia.org/w/index.php?title=Line_graph_of_a_hypergraph&oldid=1184477359」から取得