Geodesic
On the K\"onig graphs for a 5-path and~its~spanning~supergraphs
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 90-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     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\"onig 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
PB  - mathdoc
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\"onig graphs for a 5-path and~its~spanning~supergraphs
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 90-116
%V 27
%N 2
%I mathdoc
%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\"onig 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