On the \(k\)-path vertex cover of some graph products
From MaRDI portal
Publication:1759813
DOI10.1016/j.disc.2012.09.010zbMath1264.05102OpenAlexW2019831445MaRDI QIDQ1759813
Marko Jakovac, Andrej Taranenko
Publication date: 22 November 2012
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2012.09.010
upper boundsindependence numberlower boundsgraph productsvertex coverdissociation numberminimum cardinalityk-path vertex cover
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ Unnamed Item ⋮ A 2-approximation algorithm for the vertex coverP4problem in cubic graphs ⋮ On the weighted \(k\)-path vertex cover problem ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ Uniformly dissociated graphs ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Maximum induced matching of hexagonal graphs ⋮ Strong geodetic cores and Cartesian product graphs ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs
