Хордальный двудольный граф

В математической области теории графов хордальный двудольный граф — это двудольный граф B = ( X , Y , E ), в котором каждый цикл длины не менее 6 в B имеет хорду , т. е. ребро, соединяющее две вершины, которые являются расстояние > 1 друг от друга в цикле. Лучшее название было бы «слабо хордальный и двудольный», поскольку хордальные двудольные графы, как правило, не являются хордальными, как показывает индуцированный цикл длины 4.

Характеристики

Хордальные двудольные графы имеют различные характеристики с точки зрения идеального порядка исключения , гиперграфов и матриц . Они тесно связаны с сильно хордальными графами . По определению хордальные двудольные графы имеют запрещенную характеристику подграфа как графы, не содержащие любой индуцированный цикл длины 3 или длины не менее 5 (так называемые дырки) как индуцированный подграф . Таким образом, граф G является хордальным двудольным тогда и только тогда, когда G не содержит треугольников и дырок. В Golumbic (1980) упоминаются две другие характеристики: B является хордальным двудольным тогда и только тогда, когда каждый минимальный разделитель ребер индуцирует полный двудольный подграф в B тогда и только тогда, когда каждый индуцированный подграф является двудольным методом полного исключения.

Мартин Фарбер показал: Граф является сильно хордальным тогда и только тогда, когда двудольный граф инцидентности его кликового гиперграфа является хордально двудольным.

Аналогичная характеристика справедлива и для гиперграфа замкнутых окрестностей: граф является сильно хордальным тогда и только тогда, когда двудольный граф инцидентности его Гиперграф замкнутой окрестности хордально двудольный.

Другой результат, полученный Элиасом Дальхаусом, таков: Двудольный граф B = ( X , Y , E ) является хордальным двудольным тогда и только тогда, когда расщепленный граф, полученный в результате превращения X в клику, является сильно хордальным.

Двудольный граф B = ( X , Y , E ) является хордальным двудольным тогда и только тогда, когда каждый индуцированный подграф B имеет максимальный порядок X -окрестностей и максимальный порядок Y-окрестностей.

Различные результаты описывают связь между хордальными двудольными графами и полностью сбалансированными гиперграфами окрестностей двудольных графов.

Характеристика хордальных двудольных графов в терминах графов пересечений, связанных с гиперграфами, дана в .

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности тогда полностью сбалансирована и только тогда, когда матрица смежности не содержит гаммы .

Признание

Хордальные двудольные графы можно распознать за время O(min( n ² , ( n + m ) log n )) для графа с n вершинами и м края.

Сложность проблем

Различные проблемы, такие как гамильтонов цикл, Дерево Штейнера и эффективное доминирование остаются NP-полными на хордальных двудольных графах.

Различные другие проблемы, которые можно эффективно решить для двудольных графов, можно более эффективно решить для хордальных двудольных графов, как обсуждалось в разделе

Связанные классы графов

Любой хордальный двудольный граф является модулярным графом . Хордальные двудольные графы включают полные двудольные графы и двудольные дистанционно-наследственные графы .

Ссылки

• Брандштедт, Андреас (1991), «Классы двудольных графов, связанные с хордальными графами», Discrete Applied Mathematics , 32 : 51–60, doi : 10.1016/0166-218x(91)90023-p .
• Брандштедт, Андреас ; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), «Двуххордальные графы», SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137/s0895480193253415 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Драган, Федор; Волошин, Виталий (1996), «Графики инцидентности бициклических гиперграфов», Дискретная прикладная математика , 68 : 259–266, doi : 10.1016/0166-218x(95)00070-8 .
• Фарбер, М. (1983), «Характеристики сильно хордальных графов», Discrete Mathematics , 43 (2–3): 173–189, doi : 10.1016/0012-365X(83)90154-1 .
• Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN  0-12-289260-7 .
• Хуан, Цзин (2006), «Характеристики представления хордальных двудольных графов», Журнал комбинаторной теории, серия B , 96 (5): 673–683, doi : 10.1016/j.jctb.2006.01.001 .
• Лу, Чин Лунг; Тан, Чуан И (2002), «Взвешенное эффективное доминирование на некоторых совершенных графах», Discrete Applied Mathematics , 117 : 163–182, doi : 10.1016/s0166-218x(01)00184-6 .
• Любив, А. (1987), «Двойной лексический порядок матриц», SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137/0216057 .
• Мюллер, Хайко (1996), «Схемы Гамильтона в хордальных двудольных графах», Discrete Mathematics , 156 : 291–298, doi : 10.1016/0012-365x(95)00057-4 .
• Мюллер, Хайко; Брандштедт, Андреас (1987), «NP-полнота дерева Штейнера и доминирующего множества для хордальных двудольных графов», Theoretical Computer Science , 53 : 257–265, doi : 10.1016/0304-3975(87)90067-3 .
• Пейдж, Р.; Тарьян, Р.Э. (1987), «Алгоритмы уточнения трех разделов», SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137/0216062 .
• Спинрад, Джереми (1993), «Двойной лексический порядок плотных матриц 0–1», Information Processing Letters , 45 (2): 229–235, doi : 10.1016/0020-0190(93)90209-R .
• Спинрад, Джереми (2003), Эффективные представления графов , Монографии Института Филдса, Американское математическое общество, ISBN  0-8218-2815-0 .