The k-path vertex cover of rooted product graphs

DOI10.1016/J.DAM.2015.02.018zbMATH Open1315.05120OpenAlexW2125447390MaRDI QIDQ2348061FDOQ2348061

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

vertex coverindependence number\(k\)-path vertex coverdissociation numberrooted product

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Improved approximation algorithms for path vertex covers in regular graphs
• 3-path vertex cover and dissociation number of hexagonal graphs
• Spectra of M-rooted product of graphs
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• Ascending graphoidal tree cover for product graphs
• PTAS for minimum \(k\)-path vertex cover in ball graph
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Title not available (Why is that?)
• The k‐path vertex cover: General bounds and chordal graphs
• Bounds on the Twin-Width of Product Graphs

Uses Software

• NISPOC

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the \(k\)-path vertex cover of some graph products 👍 👎
• On the vertex \(k\)-path cover 👍 👎
• The well-covered dimension of products of graphs 👍 👎
• On the minimum vertex \(k\)-path cover of trees 👍 👎
• Reconfiguring \(k\)-path vertex covers 👍 👎
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs 👍 👎
• The k‐path vertex cover: General bounds and chordal graphs 👍 👎

This page was built for publication: The \(k\)-path vertex cover of rooted product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348061)