Двойственно хордальный граф

В математической области теории графов неориентированный граф G является дуально хордальным , если гиперграф его максимальных клик является гипердеревом . Название происходит от того факта, что граф является хордальным тогда и только тогда, когда гиперграф его максимальных клик является двойственным гипердереву. Первоначально эти графы определялись максимальным упорядочением окрестностей и имели множество различных характеристик. В отличие от хордальных графов, свойство быть дуально хордальным графом не является наследственным, т. е. индуцированные подграфы дуально хордального графа не обязательно являются дуально хордальными (наследственно дуально хордальные графы — это в точности сильно хордальные графы ), а дуально хордальный граф вообще является не идеальный график .

Дуальнохордальные графы появились впервые под названием HT-графы .

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

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

Следующие свойства эквивалентны:

• G имеет максимальный порядок окрестности.
• Существует остовное дерево T группы G такое, что любая максимальная клика G индуцирует поддерево в T .
• Гиперграф замкнутых окрестностей N(G) группы G является гипердеревом .
• Максимальный кликовый гиперграф группы G является гипердеревом .
• G — двухсекционный граф гипердерева .

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

В Де Кариа и Гутьеррес (2012) дуальнохордальные графы характеризуются с точки зрения свойств сепаратора.В Брешаре (2003) было показано, что дуально хордальные графы представляют собой в точности графы пересечений максимальных гиперкубов графов ациклических кубических комплексов.

Структура и алгоритмическое использование двухордальных графов даны Москарини (1993) . Это графы, которые являются хордальными и дуально хордальными.

Признание

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

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

Хотя некоторые основные проблемы, такие как максимальное независимое множество , максимальная клика , раскраска и кликовое покрытие, остаются NP-полными для дуально хордальных графов, некоторые варианты проблемы минимального доминирующего множества и дерева Штейнера эффективно решаются на дуально хордальных графах (но независимое доминирование остается NP -полный ). См. Brandstädt, Chepoi & Dragan (1999) об использовании дуальнохордального графа. свойства для ключей деревьев; см. Brandstädt, Leitert & Rautenbach (2012) для линейного по времени алгоритма эффективного доминирования и эффективное доминирование ребер на дуально хордальных графах.

Ссылки

• Брандштедт, Андреас; Чепой, Виктор; Драган, Федор (1998), «Алгоритмическое использование структуры гипердерева и максимального порядка окрестностей», Discrete Applied Mathematics , 82 (1–3): 43–77, doi : 10.1016/s0166-218x(97)00125-x .
• Брандштедт, Андреас; Чепой, Виктор; Драган, Федор (1999), «Деревья, аппроксимирующие расстояние для хордальных и дуально хордальных графов», Journal of Algorithms , 30 : 166–184, doi : 10.1006/jagm.1998.0962 .
• Брандштедт, Андреас; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), «Двуххордальные графы», SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi : 10.1137/S0895480193253415 , MR   1628114 .
• Брандштедт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Брандштедт, Андреас; Лейтерт, Арне; Раутенбах, Дитер (2012), «Эффективные доминирующие и доминирующие множества ребер для графов и гиперграфов», в Чао, Кун-Мао; Сюй, Цань-шэн; Ли, Дер-Цай (ред.), «Алгоритмы и вычисления – 23-й международный симпозиум», ISAAC 2012, Тайбэй, Тайвань, 19–21 декабря 2012 г. Труды , конспекты лекций по информатике , том. 7676, Springer, стр. 267–277, arXiv : 1207.0953 , doi : 10.1007/978-3-642-35261-4_30 .
• Брешар, Боштян (2003), «Графы пересечений максимальных гиперкубов», Европейский журнал комбинаторики , 24 (2): 195–209, doi : 10.1016/s0195-6698(02)00142-7 .
• Де Кариа, Пабло; Гутьеррес, Мариса (2012), «О минимальных вершинных разделителях дуально-хордальных графов: свойства и характеристики», Discrete Applied Mathematics , 160 (18): 2627–2635, doi : 10.1016/j.dam.2012.02.022 , hdl : 11336 /190841 .
• Драган, Федор (1989), Центры графов и свойство Хелли (на русском языке) , доктор философии. диссертация, Молдавский государственный университет, Молдова .
• Драган, Федор; Присакару, Кирилл; Чепой, Виктор (1992), "Задачи местоположения в графах и свойство Хелли (на русском языке)", Дискретная математика. (Москва) , 4 : 67–73 .
• Драган, Федор (1993), "HT-графы: центры, связное r-доминирование и деревья Штейнера", Comput. наук. Ж. Молдовы (Кишинёв) , 1 : 64–83 .
• Гутьеррес, Мариса; Обина, Л. (1996), «Метрические характеристики правильных интервальных графов и графов древовидных клик», Journal of Graph Theory , 21 (2): 199–205, doi : 10.1002/(sici)1097-0118(199602)21 :2<199::aid-jgt9>3.0.co;2-m .
• Макки, Терри А.; МакМоррис, Франция. (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям .
• Москарини, Марина (1993), «Двуххордальные графы, деревья Штейнера и связанное доминирование», Networks , 23 : 59–69, doi : 10.1002/net.3230230108 .
• Шварцфитер, Джейме Л.; Борнштейн, Клодсон Ф. (1994), «Кликовые графы хордальных и графов путей», SIAM Journal on Discrete Mathematics , 7 (2): 331–336, CiteSeerX   10.1.1.52.521 , doi : 10.1137/s0895480191223191 .