RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2020 Volume 27, Issue 2, Pages 90–116 (Mi da952)

This article is cited in 1 paper

On the König graphs for a 5-path and its spanning supergraphs

D. B. Mokeevab, D. S. Malyshevb

a Lobachevsky State University of Nizhny Novgorod, 23 Gagarin Avenue, 603950 N. Novgorod, Russia
b National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia

Abstract: 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.

UDC: 519.174.3

Received: 13.11.2018
Revised: 31.01.2020
Accepted: 19.02.2020

DOI: 10.33048/daio.2020.27.639


 English version:
Journal of Applied and Industrial Mathematics, 2020, 14:2, 367–382

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024