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

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

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

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

k一様超グラフの線グラフ、k ≥ 3

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

クラウス[ 4 ]は、グラフの線グラフをクリーク被覆によって特徴付けた。（線グラフを参照）。k≥3の任意のk一様超グラフの線グラフに対するクラウス型の大域的特徴付けは、ベルゲ[ 5 ]によって与えられた。

k一様線型ハイパーグラフの線グラフ、 k ≥ 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で分離している場合、2つの頂点が D( H ) で隣接している。[ 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 .
  • 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。
  • 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。
  • Skums, PV; Suzdal', SV; Tyshkevich, RI (2009)「線形3-ユニフォームハイパーグラフの辺交差」、離散数学、309 : 3500– 3517、doi : 10.1016/j.disc.2007.12.082。
「 https://en.wikipedia.org/w/index.php?title=Line_graph_of_a_hypergraph&oldid=1184477359」より取得