The k‐path vertex cover: General bounds and chordal graphs

DOI10.1002/NET.22079MaRDI QIDQ6087563zbMATH OpenOpenAlexFDO

Authors Csilla Bujtás, Marko Jakovac, Zsolt Tuza

Publication date 12 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.02018

zbMATH Keywords

\(k\)-path vertex coveraverage degreechordal graphplanar graphtransversalwireless sensor network

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For an integer $kge3$, a $k$-path vertex cover of a graph $G=(V,E)$ is a set $TsubseteqV$ that shares a vertex with every path subgraph of order $k$ in $G$. The minimum cardinality of a $k$-path vertex cover is denoted by $ps{i}_k(G)$. We give estimates -- mostly upper bounds -- on $ps{i}_k(G)$ in terms of various parameters, including vertex degrees and the number of vertices and edges. The problem is also considered on chordal graphs and planar graphs.

Recommendations

• Minimum \(k\)-path vertex cover
• On the k-path vertex cover of some graph products
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• On the vertex \(k\)-path cover
• 3-path vertex cover and dissociation number of hexagonal graphs

Cites work

• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
• An improved bound on the largest induced forests for triangle-free planar graphs
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs
• scientific article; zbMATH DE number 3565019 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Improved lower bounds on k‐independence
• Minimum \(k\)-path vertex cover
• New approach to the \(k\)-independence number of a graph
• New results on \(k\)-independence of graphs
• Node-Deletion Problems on Bipartite Graphs
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On maximal paths and circuits of graphs
• On the k-path vertex cover of some graph products
• On the vertex \(k\)-path cover
• On the weighted \(k\)-path vertex cover problem
• Parameterized algorithm for 3-path vertex cover
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• The \(k\)-path vertex cover of rooted product graphs
• The vertex cover \(P_3\) problem in cubic graphs
• Treewidth. Computations and approximations

Cited in

(4)

• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• The \(k\)-path vertex cover of rooted product graphs
• Dissociation in circulant graphs and integer distance graphs

This page was built for publication: The k‐path vertex cover: General bounds and chordal graphs

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