On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Autor:	D. B. Mokeev, Dmitry S. Malyshev
Rok vydání:	2021
Předmět:	Combinatorics Control and Optimization Cardinality Computer Science::Discrete Mathematics Disjoint sets Vertex (geometry) Mathematics
Zdroj:	Optimization Letters. 16:481-496
ISSN:	1862-4480 1862-4472
DOI:	10.1007/s11590-021-01771-8
Popis:	We consider graphs, which and all induced subgraphs of which possess the following property: the maximum number of disjoint paths on k vertices equals the minimum cardinality of vertex sets, covering all paths on k vertices. We call such graphs Konig for the k-path and all its spanning supergraphs. For each odd k, we reveal an infinite family of minimal forbidden subgraphs for them. Additionally, for every odd k, we present a procedure for constructing some of such graphs, based on the operations of adding terminal subgraphs and replacement of edges with subgraphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::04d949df7e62a791d7fce3d495e8418c https://doi.org/10.1007/s11590-021-01771-8 Zobrazit plný text záznamu Full text from SpringerLink