Том 26, номер 1, 2019 г., Стр. 74-88

УДК 519.174.3
Малышев Д. С., Мокеев Д. Б.
Кёниговы графы относительно 4-пути и его остовных надграфов

Аннотация:
Описывается класс графов, у которых для каждого подграфа максимальное число вершинно непересекающихся 4-путей равно минимальной мощности множества вершин таких, что каждый 4-путь подграфа содержит хотя бы одну из этих вершин. Полностью описано множество минимальных запрещённых подграфов данного класса. Кроме того, представлено альтернативное описание класса, в основе которого лежит операция подразбиения рёбер, применяемая к двудольным мультиграфам, и добавление так называемых висячих подграфов, изоморфных треугольникам и звёздам.
Ил. 1, библиогр. 19.

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

DOI: 10.33048/daio.2019.26.606

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

Статья поступила 12 декабря 2017 г.
После доработки — 30 октября 2018 г.
Принята к публикации 28 ноября 2018 г.

Литература

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

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

[3] Мокеев Д. Б. О кёниговых графах относительно $P_4$ // Дискрет. анализ и исслед. операций. 2017. T. 24, № 3. С. 61–79.

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

[5] Bre$\check{s}$ar B., Kardo$\check{s}$ F., Katreni$\check{c}$ J., Semani$\check{s}$in G. Minimum $k$-path vertex cover // Discrete Appl. Math. 2011. Vol. 159, No. 12. P. 1189–1195.

[6] Deming R. W. Independence numbers of graphs — an extension of the König-Egervary theorem // Discrete Math. 1979. Vol. 27. P. 23–33.

[7] Devi N. S., Mane A. C., Mishra S. Computational complexity of minimum $P_4$ vertex cover problem for regular and $K_{1,4}$-free graphs // Discrete Appl. Math. 2015. Vol. 184. P. 114–121.

[8] Diestel R. Graph theory. Heidelberg: Springer, 2005. (Grad. Texts Math.; Vol. 173). 322 p.

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

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

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

[12] Kardo$\check{s}$ F., Katreni$\check{c}$ J., Schiermeyer I. On computing the minimum 3-path vertex cover and dissociation number of graphs // Theor. Comput. Sci. 2011. Vol. 412, No. 50. P. 7009–7017.

[13] 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.

[14] Kosowski A., Malafiejski M., Zylinski P. Combinatorial and computational aspects of graph packing and graph decomposition // Graphs Comb. 2008. Vol. 24, No. 5. P. 461–468.

[15] Li Y., Tu J. A 2-approximation algorithm for the vertex cover $P_4$ problem in cubic graphs // Int. J. Comput. Math. 2014. Vol. 91, No. 10. P. 2103–2108.

[16] Masuyama S., Ibaraki T. Chain packing in graphs // Algorithmica. 1991. Vol. 6, No. 1. P. 826–839.

[17] Sterboul F. A Characterization of graphs in which the transversal number equals the matching number // J. Comb. Theory, Ser. B. 1979. Vol. 27. P. 228–229.

[18] Tu J., Zhou W. A primal-dual approximation algorithm for the vertex cover $P_3$ problem // Theor. Comput. Sci. 2011. Vol. 412, No. 50. P. 7044–7048.

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