König Graphs with Respect to the 4-Path and Its Spanning Supergraphs

DOI10.1134/S1990478919010101zbMath1438.05143MaRDI QIDQ4973244

Dmitriy S. Malyshev, Dmitrii Mokeev

Publication date: 2 December 2019

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

zbMATH Keywords

4-pathKönig graphsubgraph packingvertex cover of a subgraph

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (2)

On the König graphs for a 5-path and its spanning supergraphs ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

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
• Packing cycles in graphs. II
• Minimum \(k\)-path vertex cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• 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: König Graphs with Respect to the 4-Path and Its Spanning Supergraphs