Geodesic
König graphs with respect to the 4-path and its spanning supergraphs
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 74-88 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DA_2019_26_1_a4,
     author = {D. S. Malyshev and D. B. Mokeev},
     title = {K\"onig graphs with respect to the 4-path and~its~spanning supergraphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {74--88},
     year = {2019},
     volume = {26},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_1_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
AU  - D. B. Mokeev
TI  - König graphs with respect to the 4-path and its spanning supergraphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 74
EP  - 88
VL  - 26
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_1_a4/
LA  - ru
ID  - DA_2019_26_1_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%A D. B. Mokeev
%T König graphs with respect to the 4-path and its spanning supergraphs
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 74-88
%V 26
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2019_26_1_a4/
%G ru
%F DA_2019_26_1_a4
D. S. Malyshev; D. B. Mokeev. König graphs with respect to the 4-path and its spanning supergraphs. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 74-88. http://geodesic.mathdoc.fr/item/DA_2019_26_1_a4/

[1] V. E. Alekseev, D. B. Mokeev, “König graphs with respect to 3-paths”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 3–14 (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”, Discrete Math. Appl., 23:3–4 (2013), 245–249 | DOI | MR | Zbl

[3] D. B. Mokeev,, “On König graphs with respect to $P_4$”, J. Appl. Ind. Math., 11:3 (2017), 421–430 | DOI | MR | Zbl

[4] Alekseev V. E., Mokeev D. B., “König graphs for 3-paths and 3-cycles”, Discrete Appl. Math., 204 (2016), 1–5 | DOI | MR | Zbl

[5] Brešar B., Kardoš F., Katrenič J., Semanišin G., “Minimum $k$-path vertex cover”, Discrete Appl. Math., 159:12 (2011), 1189–1195 | DOI | MR | Zbl

[6] Deming R. W., “Independence numbers of graphs — an extension of the König-Egervary theorem”, Discrete Math., 27 (1979), 23–33 | DOI | MR | Zbl

[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., 184 (2015), 114–121 | DOI | MR | Zbl

[8] Diestel R., Graph theory, Grad. Texts Math., 173, Springer, Heidelberg, 2005, 322 pp. | MR | Zbl

[9] Ding G., Xu Z., Zang W., “Packing cycles in graphs, II”, J. Comb. Theory, Ser. B, 87:2 (2003), 244–253 | DOI | MR | Zbl

[10] Edmonds J., “Paths, trees, and flowers”, Can. J. Math., 17:3–4 (1965), 449–467 | DOI | MR | Zbl

[11] Hell P., “Graph packings”, Electron. Notes Discrete Math., 5 (2000), 170–173 | DOI | MR

[12] Kardoš F., Katrenič J., Schiermeyer I., “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theor. Comput. Sci., 412:50 (2011), 7009–7017 | DOI | MR | Zbl

[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), ACM, New York, 1978, 240–245 | MR | Zbl

[14] Kosowski A., Małafiejski M., Żyliński P., “Combinatorial and computational aspects of graph packing and graph decomposition”, Graphs Comb., 24:5 (2008), 461–468 | DOI | MR | Zbl

[15] Li Y., Tu J., “A 2-approximation algorithm for the vertex cover $P_4$ problem in cubic graphs”, Int. J. Comput. Math., 91:10 (2014), 2103–2108 | DOI | MR | Zbl

[16] Masuyama S., Ibaraki T., “Chain packing in graphs”, Algorithmica, 6:1 (1991), 826–839 | DOI | MR | Zbl

[17] Sterboul F., “A Characterization of graphs in which the transversal number equals the matching number”, J. Comb. Theory, Ser. B, 27 (1979), 228–229 | DOI | MR | Zbl

[18] Tu J., Zhou W., “A primal-dual approximation algorithm for the vertex cover $P_3$ problem”, Theor. Comput. Sci., 412:50 (2011), 7044–7048 | DOI | MR | Zbl

[19] Yuster R., “Combinatorial and computational aspects of graph packing and graph decomposition”, Comput. Sci. Rev., 1:1 (2007), 12–26 | DOI | MR | Zbl