Том 24, номер 1, 2017 г., Стр. 56-80

УДК 519.17
Иржавский П. А., Картынник Ю. А., Орлович Ю. Л.
1-Треугольные графы и совершенные окрестностные множества

Аннотация:
Граф называется 1-треугольным, если для любого максимального независимого множества $I$ этого графа каждое ребро графа, оба конца которого не принадлежат $I$, содержится ровно в одном треугольнике с вершиной из множества $I$. Получена характеризация 1-треугольных графов, из которой следует полиномиальный алгоритм их распознавания. Установлена сложность вычисления в классе 1-треугольных графов ряда теоретико-графовых параметров, связанных с независимостью и доминированием. В частности, установлена NP-полнота задачи о наименьшем совершенном окрестностном множестве в классе всех графов.
Библиогр. 20.

Ключевые слова: треугольный граф, рёберно-симплициальный граф, характеризация, совершенное окрестностное множество, NP-полнота.

DOI: 10.17377/daio.2017.24.532

Иржавский Павел Александрович ¹
Картынник Юрий Анатольевич ¹
Орлович Юрий Леонидович ¹
1. Белорусский гос. университет,
пр. Независимости, 4, 220030 Минск, Беларусь
е-mail: irzhavski@bsu.by, kartynnik@bsu.by, orlovich@bsu.by

Статья поступила 16 марта 2016 г.
Исправленный вариант — 27 июня 2016 г.

Литература

[1] Берж К. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962. 320 c.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[3] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.

[4] Картынник Ю. А., Орлович Ю. Л. Доминантно-треугольные графы и графы верхних границ // Докл. НАН Беларуси. 2014. Т. 58, № 1. С. 16–25.

[5] Орлович Ю. Л., Гордон В. С., Блажевич Я., Зверович И. Э., Финке Г. Независимые доминирующие и окрестностные множества в треугольных графах // Докл. НАН Беларуси. 2009. Т. 53, № 1. C. 39–44.

[6] Anbeek C., DeTemple D., McAvaney K. L., Robertson J. M. When are chordal graphs also partition graphs? // Australas. J. Comb. 1997. Vol. 16. P. 285–293.

[7] Bollobas B., Cockayne E. J. Graph-theoretic parameters concerning domination, independence, and irredundance // J. Graph Theory. 1979. Vol. 3, No. 3. P. 241–249.

[8] Boros E., Gurvich V., Milanic M. On equistable, split, CIS, and related classes of graphs // ArXiv e-prints (arXiv:1505.05683). 2015.

[9] Cheston G. A., Hare E. O., Hedetniemi S. T., Laskar R. C. Simplicial graphs // Congr. Numerantium. 1988. Vol. 67. P. 105–113.

[10] Cheston G. A., Jap T. S. A survey of the algorithmic properties of simplicial, upper bound and middle graphs // J. Graph Algorithms Appl. 2006. Vol. 10, No. 2. P. 159–190.

[11] DeTemple D., Harary F., Robertson J. M. Partition graphs // Soochow J. Math. 1987. Vol. 13, No. 2. P. 121–129.

[12] DeTemple D., Robertson J. M. Graphs associated with triangulations of lattice polygons // J. Austr. Math. Soc., Ser. A. 1989. Vol. 47, No. 3. P. 391–398.

[13] Guruswami V., Rangan C. P., Chang M. S., Chang G. J., Wong C. K. The vertex-disjoint triangles problem // Graph-Theoretic Concepts in Computer Science. Proc. 24th Int. Workshop (Smolenice Castle, Slovak Rep., June 18–20, 1998). Heidelberg: Springer, 1998. P. 26–37. (Lect. Notes Comput. Sci.;
Vol. 1517).

[14] Kloks T., Lee C.-M., Liu J., Müller H. On the recognition of general partition graphs // Graph-Theoretic Concepts in Computer Science. Proc. 29th Int. Workshop (Elspeet, The Netherlands, June 19–21, 2003), Heidelberg: Springer, 2003. P. 273–283. (Lect. Notes Comput. Sci.; Vol. 2880).

[15] McAvaney K., Robertson J., DeTemple D. A characterization and hereditary properties for partition graphs // Discrete Math. 1993. Vol. 113, No. 1. P. 131–142.

[16] Miklavic Š., Milanic M. Equistable graphs, general partition graphs, triangle graphs, and graph products // Discrete Appl. Math. 2011. Vol. 159, No. 11. P. 1148–1159.

[17] Orlovich Yu. L., Blazewicz J., Dolgui A., Finke G., Gordon V. On the complexity of the independent set problem in triangle graphs // Discrete Math. 2011. Vol. 311, No. 16. P. 1670–1680.

[18] Orlovich Yu. L., Zverovich I. E. Independent domination in triangle graphs // Electron. Notes Discrete Math. 2007. Vol. 28. P. 341–348.

[19] Sampathkumar E., Neeralagi P. S. The neighbourhood number of a graph // Indian J. Pure Appl. Math. 1985. Vol. 16. P. 126–132.

[20] Sampathkumar E., Neeralagi P. S. Independent, perfect and connected neighbourhood numbers of a graph // J. Comb. Inf. Syst. Sci. 1994. Vol. 19, No. 3–4. P. 139–145.