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

DOI10.1007/S11590-021-01771-8zbMATH Open1487.90563OpenAlexW3175559044MaRDI QIDQ2115309FDOQ2115309

Authors D. B. Mokeev, D. 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)

Recommendations

• König graphs with respect to the 4-path and its spanning supergraphs
• On the König graphs for a 5-path and its spanning supergraphs
• König graphs for 3-paths and 3-cycles
• On the Kőnig‐Egerváry theorem for ‐paths
• On König graphs with respect to \(P_4\)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6460013 (Why is no real title available?)
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A characterization of the graphs in which the transversal number equals the matching number
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Chain packing in graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Combinatorial optimization. Packing and covering
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Graph packings
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König graphs for 3-paths and 3-cycles
• König graphs with respect to the 4-path and its spanning supergraphs
• Minimum \(k\)-path vertex cover
• On König graphs with respect to \(P_4\)
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the completeness of a generalized matching problem
• Paths, Trees, and Flowers
• Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph

Cited in

(5)

• On the kings and kings-of-kings in semicomplete multipartite digraphs
• On the König graphs for a 5-path and its spanning supergraphs
• On König graphs with respect to \(P_4\)
• König graphs with respect to the 4-path and its spanning supergraphs
• König graphs for 3-paths and 3-cycles

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115309)