Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:2, 369-384
Volume 27, No 2, 2020, P. 90-116
UDC 519.174.3
D. B. Mokeev and D. S. Malyshev
On the König graphs for a 5-path and its spanning supergraphs
Abstract:
We describe the hereditary class of graphs whose every subgraph has the property that the maximum number of disjoint 5-paths (paths on 5 vertices) is equal to the minimum size of the sets of vertices having nonempty intersection with the vertex set of each 5-path. We describe this class in terms of the “forbidden subgraphs” and give an alternative description, using some operations on pseudographs.
Illustr. 2, bibliogr. 18.
Keywords: subgraph packing, vertex cover, five-vertex path, König graph.
DOI: 10.33048/daio.2020.27.639
Dmitry B. Mokeev 1,2
Dmitry S. Malyshev 2
1. Lobachevsky State University of Nizhny Novgorod,
23 Gagarin Avenue, 603950 N. Novgorod, Russia
2. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
e-mail: mokeevdb@gmail.com, dsmalyshev@rambler.ru
Received November 13, 2018
Revised January 31, 2020
Accepted February 19, 2020
References
[1] V. E. Alekseev and D. B. Mokeev, König graphs for 3-path, Diskretn. Anal. Issled. Oper. 19 (4), 3–14 (2012) [Russian].[2] V. E. Alekseev, Hereditary classes and graph encoding, Probl. Cybern. 39, 151–164 (1982) [Russian].
[3] F. Kardoš, J. Katrenic, and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theor. Comput. Sci. 412 (50), 7009–7017 (2011).
[4] Y. Li and J. Tu, A 2-approximation algorithm for the vertex cover $P_5$ problem in cubic graphs, Int. J. Comput. Math. 91 (10), 2103–2108 (2014).
[5] B. Brešar, F. Kardoš, J. Katrenic, and G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math. 159 (12), 1189–1195 (2011).
[6] J. Tu and W. Zhou, A primal-dual approximation algorithm for the vertex cover $P_3$ problem, Theor. Comput. Sci. 412 (50), 7044–7048 (2011).
[7] J. Edmonds, Paths, trees, and flowers, Can. J. Math. 17 (3–4), 449–467 (1965).
[8] D. G. Kirkpatrick and P. Hell , On the completeness of a generalized matching problem in Proc. 10th Annu. ACM Symp. Theory Comput., San Diego, CA, USA, May 1–3, 1978 (New York, ACM, 1978),
[9] S. Masuyama and T. Ibaraki, Chain packing in graph, Algorithmica 6 (1), 826–839 (1991).
[10] N. S. Devi, A. C. Mane, and S. Mishra, Computational complexity of minimum $P_5$ vertex cover problem for regular and K1,4-free graphs, Discrete Appl. Math. 184, 114–121 (2015).
[11] R. W. Deming, Independence numbers of graphs – An extension of the König–Egervary theorem, Discrete Math. 27 (1), 23–33 (1979).
[12] A. Kosowski, M. Malafiejski, and P. Zylinski, Combinatorial and computational aspects of graph packing and graph decomposition, Graphs Comb. 24 (5), 461–468 (2008).
[13.] F. Sterboul, A characterization of graphs in which the transversal number equals the matching number, J. Comb. Theory, Ser. B, 27 (2), 228–229 (1979).
[14] D. S. Malyshev and D. B. Mokeev, König graphs with respect to 4-paths and its spanning supergraphs, Diskretn. Anal. Issled. Oper. 26 (1), 74–88 (2019) [Russian].
[15] V. E. Alekseev and D. B. Mokeev, König graphs for 3-paths and 3-cycles, Discrete Appl. Math., 204, 1–5 (2016).
[16] D. B. Mokeev, On the König graphs for $P_4$, Diskretn. Anal. Issled. Oper. 24 (3), 61–79 (2017) [Russian].
[17] D. B. Mokeev, $P_q$-König extended forests and cycles in Discrete Optimization and Operations Research (Suppl. Proc. 9th Int. Conf. DOOR 2016, Vladivostok, Russia, Sept. 19–23, 2016) (RWTH Aachen Univ., Aachen, 2016), pp. 86–95 (CEUR Workshop Proc., Vol. 1623). Available at
http://ceur-ws.org/Vol-1623 (accessed May 22, 2020).
[18] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).
