Линейный график гиперграфа - Line graph of a hypergraph

В теория графов, особенно в теории гиперграфы, то линейный график гиперграфа ЧАС, обозначим 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.