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

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

Описание

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

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

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

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

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

Другой результат, найденный Элиасом Далхаусом:

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

B=(X,Y,E)

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

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

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

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

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

Распознавание

Хордальные двудольные графы могут быть распознаны за время $O(\min(n^{2},(n+m)\log n))$ для графов с n вершинами и m рёбрами .

Сложность задач

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

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

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

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

Примечания

, с. 261.
, с. 43 Definition 3.4.1.
.
Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2 N /3 вершин ( от 18 августа 2019 на Wayback Machine )
Пусть имеется граф G . Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G , называется гипреграфом максимальных клик (( , 1)).
↑ .
, с. 43 Theorem 3.4.1.
Если дан граф $G=(V,E)$ , окрестностью вершины $x\in V$ определяется как $N_{G}(x)=N(x)=\{y\in V|(x,y)\in E\}$ . Множество $N(x)$ часто называется открытой окрестностью вершины x , подчёркивая факт, что $x\notin V$ в графе без циклов. Соответственно, множество $N_{G}[x]=N[x]=N(x)\cup \{x\}$ называется замкнутой окрестностью вершины x . На вершинах V можно определить два гиперграфа, положив $N(G)=\{N(x)|x\in V\}$ и $N[G]=\{N[x]|x\in V\}$ . Первый гиперграф называется гиперграфом открытых окрестностей графа G . Второй гиперграф называется гиперграфом замкнутых окрестностей графа G ( , 7, 2.3 Neighborhood hypergraphs).
.
, с. 129 Corollary 8.3.2.
.
Цикл $(x_{1},E_{1},\dots ,x_{p},E_{p})$ гиперграфа $H(x_{i}\in V(H),E_{i}\in E(H)|i=1,\dots ,p)$ называется специальным циклом гиперграфа H . Гиперграф называется сбалансированным , если он не содержит специальных циклов нечётной длины. ( , 96)
, с. 126–127 Theorems 8.2.5, 8.2.6.
.
.
.
.
↑ .
.
.
.
от 24 августа 2019 на Wayback Machine , Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

Литература

Sylvain Gravier, Riste Škrekovski. // Preprint series. — Jadranska 19, 1111 Ljubljana, Slovenia: University of Ljubljana, Institute of Mathematics, Physics and Mechanics, 2001. — Т. 41 (2003), 890 . — ISSN .
Endre Boros, Vladimir Gurvich, Igor Zverovich. 2.3 Neighborhood hypergraphs // . — 2006. — Т. RRR 12-2006,. — (Rutcor Research Report).
J. Lehel, Zs Tuza. NEIGHBORHOOD PERFECT GRAPHS // Discrete Mathematics. — North-Holland, 1986. — Т. 61 . — С. 93—101 .
Andreas Brandstädt. Classes of bipartite graphs related to chordal graphs // . — 1991. — Т. 32 . — С. 51–60 . — doi : .
Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // . — 1998. — Т. 11 . — С. 437–455 . — doi : .
Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. . — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X .
Feodor Dragan, Vitaly Voloshin. Incidence graphs of biacyclic hypergraphs // . — 1996. — Т. 68 . — С. 259–266 . — doi : .
Farber M. Characterizations of strongly chordal graphs // Discrete Mathematics . — 1983. — Т. 43 , вып. 2–3 . — С. 173–189 . — doi : .
Martin Charles Golumbic. . — Academic Press, 1980. — ISBN 0-12-289260-7 .
Jing Huang. Representation characterizations of chordal bipartite graphs // . — 2006. — Т. 96 , вып. 5 . — С. 673–683 . — doi : .
Chin Lung Lu, Chuan Yi Tang. Weighted efficient domination on some perfect graphs // . — 2002. — Т. 117 . — С. 163–182 . — doi : .
Anna Lubiw. Doubly lexical orderings of matrices // . — 1987. — Т. 16 , вып. 5 . — С. 854–879 . — doi : .
Haiko Müller. Hamilton circuits in chordal bipartite graphs // Discrete Mathematics . — 1996. — Т. 156 . — С. 291–298 . — doi : .
Haiko Müller, Andreas Brandstädt. // . — 1987. — Т. 53 . — С. 257–265 . — doi : .
Paige R., Tarjan R. E. Three partition refinement algorithms // . — 1987. — Т. 16 , вып. 6 . — С. 973–989 . — doi : .
Jeremy Spinrad. Doubly lexical ordering of dense 0–1 matrices // . — 1993. — Т. 45 , вып. 2 . — С. 229–235 . — doi : .
Jeremy Spinrad. Efficient Graph Representations. — Fields Institute Monographs, American Mathematical Society, 2003. — ISBN 0-8218-2815-0 .