Строго хордальный граф

Неориентированный граф G называется строго хордальным, если он является хордальным и любой цикл чётной длины () в G имеет нечётную хорду, то есть ребро, которое соединяет две вершины цикла на нечётном расстоянии (>1) друг от друга[1].

Описание

Строго хордальные графы имеют описание запрещёнными графами как графы, не содержащие пророждённого цикла длиной более трёх или n-солнца () в качестве порождённого подграфа[2][3][4]. n-Солнце — это хордальный граф с 2n вершинами, разделёнными на два подмножества и так, что каждая вершина wi из W имеет ровно два соседа, ui и . n-Солнце не может быть строго хордальным, поскольку цикл … не имеет нечётных хорд.

Строго хордальные графы могут быть описаны как графы, имеющие строгий совершенный порядок исключения, порядок вершин, такой, что соседи любой вершины, которые идут в порядке позже, образуют клику, и такой, что для любых , если i-ая вершина в порядке смежна с k-ой и l-ой вершиной, а j-ая и k-ая вершины смежны, то должны быть смежны и j-ая, и l-ая вершины[3][5].

Граф строго является хордальным тогда и только тогда, когда любой из его порождённых подграфов имеет простую вершину, то есть вершину, соседи которой линейно упорядочены по порядку включения[3][6]. Также граф строго хордален тогда и только тогда, когда он хордален и любой цикл длины пять и более имеет 2-хордовый треугольник, то есть треугольник, образованный двумя хордами и ребром цикла[7].

Граф является строго хордальным тогда и только тогда, когда любой из его порождённых подграфов является двойственно хордальным графом[8].

Строго хордальные графы могут быть описаны в терминах числа полных подграфов, которым ребро принадлежит[9]. Ещё одно описание дано в статье Де Кариа и Макки[10].

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

Можно определить, является ли граф строго хордальным, за полиномиальное время путём повторяемого поиска и удаления простой вершины. Если этот процесс исключает все вершины графа, граф должен быть строго хордален. В противном случае процесс не находит подграф без простой вершины и в этом случае исходный граф не может быть строго хордален. Для строго хордального графа порядок, в котором вершины удаляются в этом процессе, называется строгим совершенным порядком исключения[3].

Известны альтернативные алгоритмы, которые могут определить, является ли граф строго хордальным и, если да, построить строгий совершенный порядок исключения более эффективно, за время для графа с n вершинами и m рёбрами[11][12][13].

Подклассы

Важным подклассом (основанным на филогении) является класс k-листовых степеней, то есть графов, образованных из листьев дерева путём соединения двух листьев ребром, если расстояние в дереве не превосходит k. Листовая степень — это граф, являющийся k-листовой степенью для некоторого k. Поскольку степени строго хордальных графов строго хордальны и деревья строго хордальны, отсюда следует, что листовые степени строго хордальны. Они образуют собственный подкласс строго хордальных графов, который, в свою очередь, включает кластерные графы как 2-листовые степени[14]. Другим важным подклассом строго хордальных графов являются интервальные графы. В статье Бранштедта, Худта, Манчини и Вагнера[15] показано, что интервальные графы и больший класс корневых ориентированных путей являются листовыми степенями.

Алгоритмические проблемы

Поскольку строго хордальные графы одновременно хордальны и двойственно хордальны, различные NP-полные задачи, такие как задача о независимом множестве, задача о клике, раскраска, задача о кликовом покрытии, доминирующее множество и задача Штейнера о минимальном дереве могут быть решены эффективно для строго хордальных графов. Задача изоморфизма графов GI-полна[16] для строго хордальных графов[17]. Поиск гамильтоновых циклов остаётся для строго хордальных расщепляемых графов NP-полной задачей[18].

Примечания

Литература

  • Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics. — 1998. Т. 11. С. 437–455. doi:10.1137/s0895480193253415.
  • Andreas Brandstädt, Christian Hundt, Federico Mancini, Peter Wagner. Rooted directed path graphs are leaf powers // Discrete Mathematics. — 2010. Т. 310. С. 897–910. doi:10.1016/j.disc.2009.10.006..
  • Andreas Brandstädt, Van Bang Le. Structure and linear time recognition of 3-leaf powers // Information Processing Letters. — 2006. Т. 98. С. 133–138. doi:10.1016/j.ipl.2006.01.004..
  • Andreas Brandstädt, Van Bang Le, Sritharan R. Structure and linear time recognition of 4-leaf powers // ACM Transactions on Algorithms. — 2008. Т. 5. С. Article 11..
  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
  • Chang G. J. K-domination and Graph Covering Problems. — Cornell University, 1982. — (Ph.D. thesis).
  • Dahlhaus E., Manuel P. D., Miller M. A characterization of strongly chordal graphs // Discrete Mathematics. — 1998. Т. 187, вып. 1–3. С. 269–271. doi:10.1016/S0012-365X(97)00268-9.
  • De Caria P., McKee T.A. Maxclique and unit disk characterizations of strongly chordal graphs // Discussiones Mathematicae Graph Theory. — 2014. Т. 34. С. 593–602. doi:10.7151/dmgt.1757..
  • Farber M. Characterizations of strongly chordal graphs // Discrete Mathematics. — 1983. Т. 43. С. 173–189. doi:10.1016/0012-365X(83)90154-1..
  • Anna Lubiw. Doubly lexical orderings of matrices // SIAM Journal on Computing. — 1987. Т. 16. С. 854–879. doi:10.1137/0216057.
  • McKee T. A. A new characterization of strongly chordal graphs // Discrete Mathematics. — 1999. Т. 205, вып. 1–3. С. 245–247. doi:10.1016/S0012-365X(99)00107-7.
  • Müller H. Hamiltonian Circuits in Chordal Bipartite Graphs // Discrete Mathematics. — 1996. Т. 156. С. 291–298. doi:10.1016/0012-365x(95)00057-4.
  • Nishimura N., Ragde P., Thilikos D.M. On graph powers for leaf-labeled trees // Journal of Algorithms. — 2002. Т. 42. С. 69–108. doi:10.1006/jagm.2001.1195.
  • Paige R., Tarjan R. E. Three partition refinement algorithms // SIAM Journal on Computing. — 1987. Т. 16. С. 973–989. doi:10.1137/0216062.
  • Rautenbach D. Some remarks about leaf roots // Discrete Mathematics. — 2006. Т. 306. С. 1456–1461. doi:10.1016/j.disc.2006.03.030.
  • Spinrad J. Doubly lexical ordering of dense 0–1 matrices // Information Processing Letters. — 1993. Т. 45. С. 229–235. doi:10.1016/0020-0190(93)90209-R.
  • Uehara R., Toda S., Nagoya T. Graph isomorphism completeness for chordal bipartite and strongly chordal graphs // Discrete Applied Mathematics. — 2005. Т. 145. С. 479–482. doi:10.1016/j.dam.2004.06.008..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.