WikiDer > Линейный график гиперграфа - Википедия

Line graph of a hypergraph - Wikipedia

В теория графов, особенно в теории гиперграфы, то линейный график гиперграфа ЧАС, обозначим L (ЧАС), это график множество вершин которого есть множество гиперребер ЧАС, с двумя смежными вершинами в L (ЧАС), когда соответствующие им гиперребра имеют непустое пересечение в ЧАС. Другими словами, L (ЧАС) это граф пересечений семейства конечных множеств. Это обобщение линейный график графа.

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

Гиперграф - это линейный если каждая пара гиперребер пересекается не более чем в одной вершине. Каждый граф является линейным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа (Берже 1989).

Линейные графики k-однородные гиперграфы, k ≥ 3

Бейнеке (1968) характеризует линейные графики графиков списком из 9 запрещенные индуцированные подграфы. (См. Статью о линейные графики.) Не известно характеризации запрещенными индуцированными подграфами линейных графов k-равномерных гиперграфов для любых k ≥ 3, и Ловас (1977) показал, что такой характеризации конечным списком не существует, если k = 3.

Крауц (1943) охарактеризованные линейные графики графиков с точки зрения клика охватывает. (Видеть Линейные графики.) Глобальная характеристика типа Крауца для линейных графов k-равномерные гиперграфы для любых k ≥ 3 было дано Берже (1989).

Линейные графики k-однородные линейные гиперграфы, k ≥ 3

Глобальная характеристика типа Крауца для линейных графиков k-равномерные линейные гиперграфы для любых k ≥ 3 было дано Naik et al. (1980). В то же время они нашли конечный список запрещенных индуцированных подграфов для линейных 3-однородных гиперграфов с минимальной степенью вершины не менее 69. Метельский и Тышкевич (1997) и Якобсон, Кезди и Лехель (1997) улучшил эту оценку до 19. Наконец Скумс, Суздаль и Тышкевич (2005) уменьшил эту оценку до 16. Метельский и Тышкевич (1997) также доказал, что если k > 3, такого конечного списка для линейных k-однородные гиперграфы, независимо от того, какая нижняя граница ставится на степень.

Трудность нахождения характеристики линейного k-равномерные гиперграфы обусловлены тем, что существует бесконечно много запрещенных индуцированных подграфов. Чтобы привести примеры, для м > 0, рассмотрим цепочку м ромбовидные графики такие, что последовательные ромбы имеют общие вершины степени два. За k ≥ 3, добавьте висячие ребра в каждую вершину степени 2 или 4, чтобы получить одно из семейств минимальных запрещенных подграфов Найка, Рао и Шриханде и др. (1980, 1982), как показано здесь. Это не исключает ни существования полиномиального распознавания, ни возможности запрещенной индуцированной характеризации подграфа, подобной характеристике Бейнеке линейных графов графов.

Повторяющийся ромбовидный graph.svg

Для линейных графиков линейных k-однородные гиперграфы различных авторов (Naik, Rao & Shrikhande et al.1980, 1982, Якобсон, Кезди и Лехель 1997, Метельский и Тышкевич 1997, и Зверович 2004) при ограничениях на минимальную степень или минимальную степень ребра G. Минимальная степень ребра не менее k3-2k2+1 в Naik et al. (1980) сокращается до 2k2-3k+1 в Якобсон, Кезди и Лехель (1997) и Зверович (2004) характеризовать линейные графики k-равномерные линейные гиперграфы для любых k ≥ 3.

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

Есть много интересных открытых проблем и предположений в Naik et al., Jacoboson et al., Metelsky et al. и Зверович.

Граф дизъюнктности

В граф дизъюнктности гиперграфа ЧАС, обозначим D (ЧАС), - граф, множество вершин которого есть множество гиперребер ЧАС, с двумя смежными вершинами в D (ЧАС), когда соответствующие им гиперребра непересекающийся в ЧАС.[1] Другими словами, D (ЧАС) это дополнительный граф из L (ЧАС). А клика в D (ЧАС) соответствует независимому множеству в L (ЧАС), наоборот.

Рекомендации

  1. ^ Мешулам, Рой (01.01.2001). «Кликовый комплекс и соответствие гиперграфа». Комбинаторика. 21 (1): 89–94. Дои:10.1007 / s004930170006. ISSN 1439-6912. S2CID 207006642.
  • Heydemann, M. C .; Сотто, Д. (1976), "Линейные графы гиперграфов II", Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Коллок. Математика. Soc. Дж. Бойяи, 18, стр. 567–582, МИСТЕР 0519291.
  • Краус, Дж. (1943), "Демонстрация новой теории Уитни сюр ле réseaux", Мат. Физ. Лапок, 50: 75–85, МИСТЕР 0018403. (На венгерском, с французским аннотацией.)
  • Ловас, Л. (1977), «Проблема 9», Beiträge zur Graphentheorie und deren Anwendungen, Vorgetragen auf dem Internationalen Kolloquium в Оберхофе (ГДР), стр. 313.
  • Naik, Ranjan N .; Rao, S. B .; Шриханде, С.С.; Сингхи, Н. М. (1980), "Графы пересечений k-равномерные гиперграфы », Комбинаторная математика, оптимальные планы и их приложения (Proc. Sympos. Combin. Math. And Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978), Анналы дискретной математики, 6, стр. 275–279, МИСТЕР 0593539.
  • Skums, P. V .; Суздаль, С. В .; Тышкевич, Р. И. (2009), "Пересечение ребер линейных 3-однородных гиперграфов", Дискретная математика, 309: 3500–3517, Дои:10.1016 / j.disc.2007.12.082.