Линейный график гиперграфа

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

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

Гиперграф называется линейным , если каждая пара гиперребер пересекается не более чем в одной вершине. Каждый граф является линейным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа. ^{[ 1 ]}

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

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

Краусс ^{[ 4 ]} охарактеризованы линейные графы графов в терминах кликовых покрытий. (См. Линейные графы .) Глобальная характеристика типа Крауша для линейных графов k -однородных гиперграфов для любого k ≥ 3 была дана Берже. ^{[ 5 ]}

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

Глобальная характеристика типа Крауса для линейных графов k -однородных линейных гиперграфов для любого k ≥ 3 была дана Найком, Рао, Шрикханде и Сингхи. ^{[ 6 ]} В то же время они нашли конечный список запрещенных индуцированных подграфов для линейных 3-однородных гиперграфов с минимальной степенью вершины не ниже 69. Метельский |1 и Тышкевич ^{[ 7 ]} и Якобсон, Кезди и Лехель ^{[ 8 ]} улучшили эту оценку до 19. Наконец, Скумс, Суздаль и Тышкевич. ^{[ 9 ]} сократили эту оценку до 16. Метельский и Тышкевич. ^{[ 10 ]} также доказал, что если k > 3, такого конечного списка не существует для линейных k -однородных гиперграфов, независимо от того, какая нижняя граница установлена на степень.

Трудность описания линейных k -однородных гиперграфов связана с тем, что существует бесконечное число запрещенных индуцированных подграфов. В качестве примеров для m > 0 рассмотрим цепочку из m ромбовидных графов , в которой последовательные ромбы имеют общие вершины второй степени. Для k ≥ 3 добавьте висячие ребра в каждую вершину степени 2 или 4, чтобы получить одно из семейств минимальных запрещенных подграфов Наика, Рао, Шрикханде и Сингхи. ^{[ 11 ]} как показано здесь. Это не исключает ни существования полиномиального распознавания, ни возможности характеризации запрещенного индуцированного подграфа, аналогичной линейным графам Бейнеке.

Существуют некоторые интересные характеристики линейных графов линейных k -однородных гиперграфов, принадлежащие различным авторам. ^{[ 12 ]} при ограничениях на минимальную степень или минимальную степень ребра G. Минимальная степень ребра не менее k ³-2-2к ²+1 в Наике, Рао, Шрикханде и Сингхи ^{[ 13 ]} снижается до 2 тыс. ²-3 тыс. +1 в Якобсоне, Кезди и Леэле ^{[ 14 ]} и Зверович ^{[ 15 ]} охарактеризовать линейные графы k -однородных линейных гиперграфов для любого k ≥ 3.

Сложность распознавания линейных графов линейных k -однородных гиперграфов без каких-либо ограничений на минимальную степень (или минимальную степень ребра) неизвестна. При k = 3 и минимальной степени не ниже 19 распознавание возможно за полиномиальное время. ^{[ 16 ]} Skums, Suzdal', and Tyshkevich ^{[ 17 ]} снизил минимальную степень до 10.

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

Граф непересекаемости

Граф дизъюнктности гиперграфа H , обозначаемый D( H ), — это граф, множество вершин которого представляет собой множество гиперребер H , с двумя вершинами, смежными в D( H , когда их соответствующие гиперребра не пересекаются в H. ) ^{[ 18 ]} Другими словами, D( H ) является графом дополнений L( H ). Клика H в D( H ) соответствует независимому множеству в L( ) , и наоборот.

Ссылки

^ ( Горы 1989 )
^ Бейнеке (1968)
^ Всадник (1977)
^ Краусс (1943)
^ Горы (1989)
^ Наик и др. (1980)
^ Метельский и Тышкевич (1997)
^ Джейкобсон, Кезди и Лехель (1997)
^ Skums, Suzdal' & Tyshkevich (2009)
^ Метельский и Тышкевич (1997)
^ Наик и др. (1980) , Найк и др. (1982)
^ Наик и др. (1980) , Найк и др. (1982) , Якобсон, Кезди и Лехель 1997 , Метельский и Тышкевич 1997 и Зверович 2004
^ Наик и др. (1980)
^ Джейкобсон, Кезди и Лехель (1997)
^ Зверович (2004)
^ Якобсон, Кезди и Лехель 1997 и Метельский и Тышкевич 1997
^ Skums, Suzdal' & Tyshkevich (2009)
^ Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

Бейнеке, Л.В. (1968), «О производных графах и орграфах», в Саксе, Х.; Восс, Х.; Вальтер, Х. (ред.), Вклад в теорию графов , Лейпциг: Тойбнер, стр. 17–23 .
Берге, К. (1989), Гиперграфы: комбинаторика конечных множеств , Амстердам: Северная Голландия, MR 1013569 . Переведено с французского.
Бермонд, Дж. К.; Хайдеманн, MC; Сотто, Д. (1977), «Линейные графики гиперграфов I» (PDF) , Discrete Mathematics , 18 (3): 235–241, doi : 10.1016/0012-365X(77)90127-3 , MR 0463003 .

Хайдеманн, MC; Сотто, Д. (1976), «Линейные графики гиперграфов II», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976) , коллоквиум. Математика. Соц. Дж. Боляи, вып. 18, стр. 567–582, МР 0519291 .

Крауш Дж. (1943), “Новое доказательство теоремы Уитни о сетях”, Матем. Физ. Лапок , 50 : 75–85, МР 0018403 . (На венгерском языке, с аннотацией на французском языке.)

Ловас, Л. (1977), «Проблема 9», вклад в теорию графов и ее приложения , представленный на Международном коллоквиуме в Оберхофе (ГДР), с. 313 .

Джейкобсон, MS; Кезди, Андре Э.; Лехель, Йено (1997), «Распознавание графов пересечений линейных однородных гиперграфов», Graphs and Combinatorics , 13 (4): 359–367, doi : 10.1007/BF03353014 , MR 1485929 , S2CID 9173731 .

Метельский, Юрий; Тышкевич, Регина (1997), «Линейные графы линейных 3-однородных гиперграфов», Журнал теории графов , 25 (4): 243–251, doi : 10.1002/(SICI)1097-0118(199708)25:4< 243::AID-JGT1>3.0.CO;2-K , MR 1459889 .

Наик, Ранджан Н.; Рао, СБ; Шрикханде, SS ; Сингхи, Н.М. (1980), «Графы пересечений k -однородных гиперграфов», Комбинаторная математика, оптимальные планы и их приложения (Proc. Sympos. Combin. Math. and Optimal Design, Университет штата Колорадо, Форт-Коллинз, Колорадо, 1978). ) , Анналы дискретной математики, вып. 6, стр. 275–279, МР 0593539 .

Наик, Ранджан Н.; Рао, СБ; Шрикханде, SS ; Сингхи, Н.М. (1982), «Графы пересечений k -однородных линейных гиперграфов», European Journal of Combinatorics , 3 (2): 159–172, doi : 10.1016/s0195-6698(82)80029-2 , MR 0670849 .

Скумс, П.В.; Суздаль, СВ; Тышкевич, Р.И. (2009), «Пересечение ребер линейных 3-однородных гиперграфов», Дискретная математика , 309 : 3500–3517, doi : 10.1016/j.disc.2007.12.082 .

Зверович, Игорь Е. (2004), «Решение проблемы Якобсона, Кезди и Лехеля», Графы и комбинаторика , 20 (4): 571–577, doi : 10.1007/s00373-004-0572-1 , MR 2108401 , S2CID 33662052 .

Волошин, Виталий И. (2009), Введение в теорию графов и гиперграфов , Нью-Йорк: Nova Science Publishers, Inc. , MR 2514872

[1] ( Горы 1989 )

[2] Бейнеке (1968)

[3] Всадник (1977)

[4] Краусс (1943)

[5] Горы (1989)

[6] Наик и др. (1980)

[7] Метельский и Тышкевич (1997)

[8] Джейкобсон, Кезди и Лехель (1997)

[9] Skums, Suzdal' & Tyshkevich (2009)

[10] Метельский и Тышкевич (1997)

[11] Наик и др. (1980) , Найк и др. (1982)

[12] Наик и др. (1980) , Найк и др. (1982) , Якобсон, Кезди и Лехель 1997 , Метельский и Тышкевич 1997 и Зверович 2004

[13] Наик и др. (1980)

[14] Джейкобсон, Кезди и Лехель (1997)

[15] Зверович (2004)

[16] Якобсон, Кезди и Лехель 1997 и Метельский и Тышкевич 1997

[17] Skums, Suzdal' & Tyshkevich (2009)

[18] Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]