EN|RU
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
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 Received December 12, 2017 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. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|