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

DOI10.1007/s11590-021-01771-8zbMath1487.90563OpenAlexW3175559044MaRDI QIDQ2115309

Dmitrii Mokeev, Dmitriy S. Malyshev

Publication date: 15 March 2022

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-021-01771-8

zbMATH Keywords

constructive descriptionminimal forbidden subgraph\(k\)-path cover\(k\)-path packing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• König graphs for 3-paths and 3-cycles
• Combinatorial and computational aspects of graph packing and graph decomposition
• A characterization of the graphs in which the transversal number equals the matching number
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Chain packing in graphs
• Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• Minimum \(k\)-path vertex cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Combinatorial Optimization
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• König Graphs with Respect to the 4-Path and Its Spanning Supergraphs
• Paths, Trees, and Flowers
• On König graphs with respect to P4
• On the completeness of a generalized matching problem

This page was built for publication: On partial descriptions of König graphs for odd paths and all their spanning supergraphs