Geodesic
On the König graphs for a 5-path and its spanning supergraphs
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 90-116 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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

[1] V. E. Alekseev, D. B. Mokeev, “König graphs for $3$-path”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 3–14 (in Russian) | MR | Zbl

[2] V. E. Alekseev, “Hereditary classes and graph encoding”, Probl. Cybern., 39 (1982), 151–164 (in Russian) | Zbl

[3] 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

[4] Li Y., Tu J., “A $2$-approximation algorithm for the vertex cover $P_5$ problem in cubic graphs”, Int. J. Comput. Math., 91:10 (2014), 2103–2108 | 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] 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

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

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

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

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

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

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

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

[14] D. S. Malyshev, D. B. Mokeev, “König graphs with respect to $4$-paths and its spanning supergraphs”, Diskretn. Anal. Issled. Oper., 26:1 (2019), 74–88 (in Russian) | Zbl

[15] 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

[16] D. B. Mokeev, “On the König graphs for $P_4$”, Diskretn. Anal. Issled. Oper., 24:3 (2017), 61–79 (in Russian) | MR | Zbl

[17] Mokeev D. B., “$P_q$-König extended forests and cycles”, Discrete Optimization and Operations Research, Suppl. Proc. 9th Int. Conf. DOOR 2016 (Vladivostok, Russia, Sept. 19–23, 2016), CEUR Workshop Proc., 1623, RWTH Aachen Univ., Aachen, 2016, 86–95 (accessed May 22, 2020) http://ceur-ws.org/Vol-1623

[18] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR | MR