Том 27, номер 2, 2020 г., Стр. 90-116

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

Аннотация:
Описывается наследственный класс графов, обладающих свойством равенства максимального числа вершинно не пересекающихся 5-путей (путей из 5 вершин) и минимальной мощности множества вершин, имеющего непустое пересечение с множеством вершин каждого 5-пути. Дано описание данного класса в терминах «запрещённых подграфов», а также альтернативное описание класса, в основе которого лежит построение графов из псевдографов с использованием различных операций.
Ил. 2, библиогр. 18.

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

DOI: 10.33048/daio.2020.27.639

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

Статья поступила 13 ноября 2018 г.
После доработки — 31 января 2020 г.
Принята к публикации 19 февраля 2020 г.

Литература

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

[2] Алексеев В. Е. Наследственные классы и кодирование графов //Пробл. кибернетики. 1982. Т. 39. С. 151–164.

[3] Kardoš F., Katrenic 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.

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

[5] Brešar B., Kardoš F., Katrenic J., Semanišin G. Minimum $k$-path vertex cover // Discrete Appl. Math. 2011. Vol. 159, No. 12. P. 1189–1195.

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

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

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

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

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

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

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

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

[14] Малышев Д. С., Мокеев Д. Б. Кёниговы графы относительно 4-пути и его остовных надграфов // Дискрет. анализ и исслед. операций. 2019. T. 26, № 1. С. 74–88.

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

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

[17] Mokeev D. B. $P_q$-König extended forests and cycles // Suppl. Proc. 9th Int. Conf. Discrete Optimization and Operations Research and Sci. School (DOOR 2016). CEUR-WS. 2016. Vol. 1623. P. 86–95.

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