Email this article König Graphs with Respect to the 4-Path and Its Spanning Supergraphs
- Authors: Malyshev D.S.1, Mokeev D.B.2,1
-
Affiliations:
- National Research University Higher School of Economics
- Lobachevsky State University of Nizhny Novgorod
- Issue: Vol 13, No 1 (2019)
- Pages: 85-92
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213147
- DOI: https://doi.org/10.1134/S1990478919010101
- ID: 213147
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
Keywords
About the authors
D. S. Malyshev
National Research University Higher School of Economics
Author for correspondence.
Email: dsmalyshev@rambler.ru
Russian Federation, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155
D. B. Mokeev
Lobachevsky State University of Nizhny Novgorod; National Research University Higher School of Economics
Author for correspondence.
Email: MokeevDB@gmail.com
Russian Federation, pr. Gagarina 23, Nizhny Novgorod, 603950; ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155
