König Graphs with Respect to the 4-Path and Its Spanning Supergraphs
- Авторы: Malyshev D.1, Mokeev D.2,1
-
Учреждения:
- National Research University Higher School of Economics
- Lobachevsky State University of Nizhny Novgorod
- Выпуск: Том 13, № 1 (2019)
- Страницы: 85-92
- Раздел: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213147
- DOI: https://doi.org/10.1134/S1990478919010101
- ID: 213147
Цитировать
Аннотация
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.
Ключевые слова
Об авторах
D. Malyshev
National Research University Higher School of Economics
Автор, ответственный за переписку.
Email: dsmalyshev@rambler.ru
Россия, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155
D. Mokeev
Lobachevsky State University of Nizhny Novgorod; National Research University Higher School of Economics
Автор, ответственный за переписку.
Email: MokeevDB@gmail.com
Россия, pr. Gagarina 23, Nizhny Novgorod, 603950; ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155