Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:1, 85-92
Volume 26, No 1, 2019, P. 74-88
UDC 519.174.3
D. S. Malyshev and D. B. Mokeev
König graphs with respect to the 4-path and its spanning supergraphs
Abstract:
We describe the class of graphs whose every subgraph has the next property: The maximal number of disjoint 4-paths is equal to the minimal cardinality of sets of vertices such that every 4-path in the subgraph contains at least one of these vertices. We completely describe the set of minimal forbidden subgraphs for this class. Moreover, we present an alternative description of the class based on the operations of edge subdivision applied to bipartite multigraphs and the addition of the so-called pendant subgraphs, isomorphic to triangles and stars.
Illustr. 1, bibliogr. 19.
Keywords: subgraph packing, vertex cover of a subgraph, 4-path, König graph.
DOI: 10.33048/daio.2019.26.606
Dmitry S. Malyshev 1,2
Dmitry B. Mokeev 1,2
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
2. Lobachevsky Nizhny Novgorod State University,
23 Gagarin Avenue, 603950 Nizhny Novgorod, Russia
e-mail: dsmalyshev@rambler.ru, MokeevDB@gmail.com
Received December 12, 2017
Revised October 30, 2018
Accepted November 28, 2018
References
[1] V. E. Alekseev and D. B. Mokeev, König graphs with respect to 3-paths, Diskretn. Anal. Issled. Oper., 19, No. 4, 3–14, 2012 [Russian].[2] D. S. Malyshev, The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem, Diskretn. Mat., 25, No. 2, 63–67, 2013 [Russian]. Translated in Discrete Math. Appl., 23, No. 3–4, 245–249, 2013.
[3] D. B. Mokeev, On König graphs with respect to $P_4$, Diskretn. Anal. Issled. Oper., 24, No. 3, 61–79, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 3, 421–430, 2017.
[4] V. E. Alekseev and D. B. Mokeev, König graphs for 3-paths and 3-cycles, Discrete Appl. Math., 204, 1–5, 2016.
[5] B. Brešar, F. Kardoš, J. Katrenic, and G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math., 159, No. 12, 1189–1195, 2011.
[6] R. W. Deming, Independence numbers of graphs – an extension of the König–Egervary theorem, Discrete Math., 27, 23–33, 1979.
[7] N. S. Devi, A. C. Mane, and S. Mishra, Computational complexity of minimum $P_4$ vertex cover problem for regular and K1,4-free graphs, Discrete Appl. Math., 184, No. 12, 114–121, 2015.
[8] R. Diestel, Graph Theory, Springer, Heidelberg, 2005 (Grad. Texts Math., Vol. 173).
[9] G. Ding, Z. Xu, and W. Zang, Packing cycles in graphs, II, J. Comb. Theory, Ser. B, 87, No. 2, 244–253, 2003.
[10] J. Edmonds, Paths, trees, and flowers, Can. J. Math., 17, No. 3–4, 449–467, 1965.
[11] P. Hell, Graph packings, Electron. Notes Discrete Math., 5, 170–173, 2000.
[12] F. Kardoš, J. Katrenic, and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theor. Comput. Sci., 412, No. 50, 7009–7017, 2011.
[13] D. G. Kirkpatrick and P. Hell, On the completeness of a generalized matching problem, in Proc. X Annu. ACM Symp. Theory Comput., San Diego, USA, May 1–3, 1978, pp. 240–245, ACM, New York, 1978.
[14] A. Kosowski, M. Malafiejski, and P. Zylinski, Combinatorial and computational aspects of graph packing and graph decomposition, Graphs Comb., 24, No. 5, 461–468, 2008.
[15] Y. Li and J. Tu, A 2-approximation algorithm for the vertex cover $P_4$ problem in cubic graphs, Int. J. Comput. Math., 91, No. 10, 2103–2108, 2014.
[16] S. Masuyama and T. Ibaraki, Chain packing in graphs, Algorithmica, 6, No. 1, 826–839, 1991.
[17] F. Sterboul, A characterization of graphs in which the transversal number equals the matching number, J. Comb. Theory, Ser. B, 27, No. 2, 228–229, 1979.
[18] J. Tu and W. Zhou, A primal-dual approximation algorithm for the vertex cover $P_3$ problem, Theor. Comput. Sci., 412, No. 50, 7044–7048, 2011.
[19] R. Yuster, Combinatorial and computational aspects of graph packing and graph decomposition, Comput. Sci. Rev., 1, No. 1, 12–26, 2007.
