The \(k\)-path vertex cover of rooted product graphs

DOI10.1016/j.dam.2015.02.018zbMath1315.05120OpenAlexW2125447390MaRDI QIDQ2348061

Marko Jakovac

Publication date: 10 June 2015

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

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

zbMATH Keywords

independence numbervertex cover\(k\)-path vertex coverdissociation numberrooted product

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Unnamed Item ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ Spectra of M-rooted product of graphs

Uses Software

• NISPOC

Cites Work

• Unnamed Item
• 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
• The independence polynomial of rooted products of graphs
• The independence number in graphs of maximum degree three
• On graphs having domination number half their order
• Products of graceful trees
• The independence number of graphs in terms of degrees
• The independence number of the strong product of odd cycles
• On the \(k\)-path vertex cover of some graph products
• The chromatic number and other functions of the lexicographic product
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• NP-hard graph problems and boundary classes of graphs
• Independent packings in structured graphs
• On F-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• A new graph product and its spectrum
• On the independence number of a graph in terms of order and size