• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On the Konig graphs for the 5-path and its spanning supergraphs

Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 2. P. 369-384.

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.