Рёберный граф гиперграфа

Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.

Вопросы о рёберных графах гиперграфов часто являются обобщениями вопросов о рёберных графах обычных графов. Например, гиперграф, все рёбра которого имеют размер k, называется k-униформным' (2-униформный гиперграф — это обычный граф). В теории гиперграфов часто естественно требовать k-униформность. Любой обычный граф является рёберным графом некоего гиперграфа, но если зафиксировать размер ребра k (число точек множества, принадлежащего ребру), не всякий граф является рёберным графом какого-либо k-униформного графа. Основная задача — описать рёберные графы для каждого $k\geqslant 3$.

Гиперграф называется линейным, если любая пара гиперрёбер имеет в пересечении максимум одну вершину. Любой граф является рёберным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа.

Рёберные графы k-униформных гиперграфов, $k\geqslant 3$

Байнеке описал рёберные графы обычных графов путём перечисления 9 запрещённых порождённых подграфов (смотрите статью о рёберных графах). Никакого описания посредством запрещённых порождённых подграфов не известно для рёберных графов k-униформных гиперграфов для любого $k\geqslant 3$ и Ловас показал, что не существует такого описания в виде конечного списка для k = 3.

Краус описал рёберные графы обычных графов в терминах покрытия кликами (Смотрите Рёберный граф). Глобальное описание краусовского типа для рёберных графов k-униформных гиперграфов для любого $k\geqslant 3$ дано Бержем.

Рёберные графы k-униформных линейных гиперграфов для $k\geqslant 3$

Глобальное описание краусовского типа для рёберных графов k-униформных линейных гиперграфов для любого $k\geqslant 3$ дано Найком, Рао, Шрикханде и Сингхи. В то же время они нашли конечное число запрещённых порождённых подграфов для линейных 3-униформных гиперграфов с минимальной степенью вершины не меньше 69. Метельский и Тышкевич и Якобсон, Кезди, Лехель улучшили эту границу до 19, а Скумс, Суздаль и Тышкевич сократили это значение до 16. Метельский и Тышкевич также доказали, что для k > 3 не существует подобного списка для линейных k-униформных гиперграфов, какое бы ограничение на степень не накладывали.

Сложность поиска описания линейных k-униформных гиперграфов заключается в том, что имеется бесконечно много запрещённых порождённых подграфов. Чтобы дать пример, для m > 0 возьмём цепочку из m графов-алмазов, так чтобы алмазы имели общие вершины второго порядка, и добавим некоторые висячие вершины, как показано на рисунке, чтобы получить одно из семейств минимальных запрещённых подграфов.

Имеется ряд интересных описаний для рёберных графов линейных k-униформных гиперграфов, данных разными авторами, при ограничениях на минимальную степень вершин или минимальную степень рёбер. Минимальная степень ребра для описания рёберных графов k-униформных линейных гиперграфов для любого $k\geqslant 3$, не меньшая $k^{3}-2k^{2}+1$ в работе Найка, Рао, Шрикханде и Сигхи, уменьшена до $2k^{2}-3k+1$ в работах Якобсона, Кезди, Лехела и Зверовича.

Сложность распознавания рёберных графов линейных k-униформных гиперграфов без ограничений на минимальную степень (или минимальную степень рёбер) неизвестна. Для k = 3 и минимальной степени по меньшей мере 19 распознавания возможно за полиномиальное время). Скумс, Суздаль и Тышкевич уменьшили минимальную степень до 10.

Есть много нерешённых задач и гипотез в работах Найка и др., Якобсона и др., Метельского и др. и Зверовича.

Литература

• L. W. Beineke. Beitrage zur Graphentheorie / H. Sachs, H. Voss, H. Walther. — Leipzig: Teubner, 1968. — С. 17—23.
• C. Berge. Hypergraphs: Combinatorics of Finite Sets. — North-Holland, 1989.. Переведено с французского
• J. C. Bermond, M. C. Heydemann, D. Sotteau. Line graphs of hypergraphs I // Discrete Mathematics. — 1977. — Т. 18. — С. 235—241. — doi:10.1016/0012-365X(77)90127-3.
• M. C. Heydemann, D. Sotteau. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976). — 1976. — Т. 18. — С. 567—582.
• J. Krausz. Démonstration nouvelle d'une théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. — 1943. — Т. 50. — С. 75—85.. На венгерском
• L. Lovász. Beitrage zur Graphentheorie und deren Ansendungen. — 1977. — С. 313.
• M. S. Jacobson, Andre E. Kézdy, Jeno Lehel. Recognizing intersection graphs of linear uniform hypergraphs // Graphs and Combinatorics. — 1997. — Т. 13. — С. 359—367.
• Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Т. 25. — С. 243—251. — doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
• Метельский Ю.М., Тышкевич Р.И. Реберные графы линейны: З-униформных гиперграфов // Докл. АН Беларус. — 1996. — С. 26—30.
• Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). — 1980. — Т. 6. — С. 275—279.
• Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Intersection graphs of k-uniform linear hypergraphs // European J. Combinatorics. — 1982. — Т. 3. — С. 159—172. — doi:10.1016/s0195-6698(82)80029-2.
• P. V. Skums, S. V. Suzdal', R. I. Tyshkevich. Edge intersection of linear 3-uniform hypergraphs // Discrete Mathematics. — 2009. — Т. 309. — С. 3500—3517. — doi:10.1016/j.disc.2007.12.082.
• Igor E. Zverovich. A solution to a problem of Jacobson, Kézdy and Lehel // Graphs and Combinatorics. — 2004. — Т. 20. — С. 571—577. — doi:10.1007/s00373-004-0572-1.
• Vitaly I. Voloshin. Introduction to Graph and Hypergraph Theory. — Nova Science Publishers, Inc., 2009.