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

Описание

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

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

• G имеет упорядочения максимального соседства ( англ. maximum neighborhood ordering ) .
• Есть остовное дерево T графа G такое, что любая максимальная клика графа G порождает поддерево в T .
• Гиперграф замкнутого соседства N(G) графа G является .
• Гиперграф максимальных клик графа G является .
• G является 2-секционным графом .

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

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

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

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

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

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

В то время как основные задачи, такие как поиск максимального независимого множества , максимальной клики , раскраски и кликового покрытия остаются NP-полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов (но задача независимого доминирования остаётся NP-полной ) . См. статью Бранштэдта, Чепоя и Драгана для использования свойств двойственных хордальных графов для задач с остовными деревьями, и статью Бранштэдта, Ляйтерта и Раутенбаха для алгоритма линейного времени поиска доминирования вершин и рёбер.

Примечания

Литература

• Terry A. McKee, McMorris F. R. Topics in Intersection Graph Theory. — SIAM Monographs on Discrete Mathematics and Applications, 1999.