Том 24, номер 3, 2017 г., Стр. 61-79

УДК 519.174.3
Мокеев Д. Б.
О кёниговых графах относительно $P_4$

Аннотация:
Описывается класс графов, у которых для каждого порождённого подграфа максимальное число непересекающихся порождённых путей с четырьмя вершинами равно минимальной мощности множества вершин таких, что каждый такой путь содержит хотя бы одну из них. В основе описания лежит операция замены вершин кографами, применяемая к вершинам графов, полученных из двудольных графов подразбиением их цикловых рёбер.
Библиогр. 13.

Ключевые слова: упаковка подграфов, вершинное покрытие подграфов, четырёхвершинный путь, кёнигов граф.

DOI: 10.17377/daio.2017.24.561

Мокеев Дмитрий Борисович ^1,2
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
2. НИУ Высшая школа экономики в Нижнем Новгороде,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
е-mail: MokeevDB@gmail.com

Статья поступила 30 декабря 2016 г.
Исправленный вариант — 24 января 2017 г.

Литература

[1] Алексеев В. Е., Мокеев Д. Б. Кёниговы графы относительно 3-пути // Дискрет. анализ и исслед. операций. 2012. T. 19, № 4. С. 3–14.

[2] Малышев Д. С. Влияние роста упаковочного числа графов на сложность задачи о независимом множестве // Дискрет. математика. 2013. Т. 25, № 2. С. 63–67.

[3] Малышев Д. С. Критические классы графов для задачи о рёберном списковом ранжировании // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 59–76.

[4] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. 2004. Vol. 132, No. 1–3. P. 17–26.

[5] Alekseev V. E., Mokeev D. B. König graphs for 3-paths and 3-cycles // Discrete Appl. Math. 2016. Vol. 204. P. 1–5

[6] Corneil D. G., Lerchs H., Stewart Burlingham L. Complement reducible graphs // Discrete Appl. Math. 1981. Vol. 3, No. 3. P. 163–174

[7] Ding G., Xu Z., Zang W. Packing cycles in graphs, II // J. Comb. Theory, Ser. B. 2003. Vol. 87, No. 2.
P. 244–253.

[8] Edmonds J. Paths, trees, and flowers //Can. J.Math. 1965. Vol. 17, No. 3–4. P. 449–467.

[9] Hell P. Graph packings // Electron. Notes Discrete Math. 2000. Vol. 5. P. 170–173

[10] Kirkpatrick D. G., Hell P. On the completeness of a generalized matching problem // Proc. 10th Annu. ACM Symp. Theory Comput. (San Diego, CA, May 1–3, 1978). New York: ACM, 1978. P. 240–245.

[11] Mahadev N. V. R., Peled U. N. Threshold graphs and related topics. Amsterdam: North-Holland, 1995, 543 p. (Ann. Discrete Math.; Vol. 56).

[12] Mokeev D. B. König graphs for 4-paths // Models, Algorithms and Technologies for Network Analysis (Proc. 3rd Int. Conf. Network Analysis, Nizhny Novgorod, Russia, May 20–22, 2013). Cham: Springer, 2014. P. 93–103. (Springer Proc. Math. Stat.; Vol. 104).

[13] Yuster R. Combinatorial and computational aspects of graph packing and graph decomposition // Comput. Sci. Rev. 2007. Vol. 1, No. 1. P. 12–26.