König Graphs with Respect to the 4-Path and Its Spanning Supergraphs
- Autores: Malyshev D.1, Mokeev D.2,1
-
Afiliações:
- National Research University Higher School of Economics
- Lobachevsky State University of Nizhny Novgorod
- Edição: Volume 13, Nº 1 (2019)
- Páginas: 85-92
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213147
- DOI: https://doi.org/10.1134/S1990478919010101
- ID: 213147
Citar
Resumo
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.
Palavras-chave
Sobre autores
D. Malyshev
National Research University Higher School of Economics
Autor responsável pela correspondência
Email: dsmalyshev@rambler.ru
Rússia, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155
D. Mokeev
Lobachevsky State University of Nizhny Novgorod; National Research University Higher School of Economics
Autor responsável pela correspondência
Email: MokeevDB@gmail.com
Rússia, pr. Gagarina 23, Nizhny Novgorod, 603950; ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155