On the \(k\)-path vertex cover of some graph products

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

zbMATH Keywords

upper boundsindependence numberlower boundsgraph productsvertex coverdissociation numberminimum cardinalityk-path vertex cover

Mathematics Subject Classification ID

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 coverP₄problem 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