König graphs for 3-paths and 3-cycles

DOI10.1016/J.DAM.2015.10.002MaRDI QIDQ266789zbMATH OpenOpenAlexFDO

Authors V. E. Alekseev, D. B. Mokeev

Publication date 7 April 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.10.002

zbMATH Keywords

\(P_3\)-cover\(P_3\)-packingKönig graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• On the Kőnig‐Egerváry theorem for ‐paths
• On König graphs with respect to \(P_4\)
• König Graphs for 4-Paths
• Tractability of König edge deletion problems

Cites work

• scientific article; zbMATH DE number 6460013 (Why is no real title available?)
• A simple test on 2-vertex- and 2-edge-connectivity
• Geometric algorithms and combinatorial optimization.
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Matching theory
• Packing cycles in graphs. II
• The complexity of König subgraph problems and above-guarantee vertex cover

Cited in

(8)

• 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
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• Forbidden subgraphs and the Kőnig property
• König Graphs for 4-Paths
• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• Tractability of König edge deletion problems

This page was built for publication: König graphs for 3-paths and 3-cycles

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