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

DOI10.1016/j.dam.2015.10.002zbMath1333.05157OpenAlexW1884765930MaRDI QIDQ266789

Vladimir E. Alekseev, Dmitrii 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)

Related Items (5)

On the König graphs for a 5-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 ⋮ On König graphs with respect to P4 ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

• Unnamed Item
• The complexity of König subgraph problems and above-guarantee vertex cover
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Geometric algorithms and combinatorial optimization.
• Packing cycles in graphs. II
• A simple test on 2-vertex- and 2-edge-connectivity

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