The k-path vertex cover: general bounds and chordal graphs

2021/05/05 by Bujtás, Csilla, Jakovac, Marko, Tuza, Zsolt
#05C38 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2105.02018

Abstract

For an integer k≥ 3, a k-path vertex cover of a graph G=(V,E) is a set T⊆ V 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 ψ_k(G). We give estimates -- mostly upper bounds -- on ψ_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.

Related

• A Survey on the k-Path Vertex Cover Problem
• A new lower bound for eternal vertex cover number
• On Gallai's conjecture for series-parallel graphs and planar 3-trees
• A tight Q-index condition for a graph to be k-path-coverable involving minimum degree
• Parameterized algorithm for 3-path vertex cover