| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419606 | Discrete Applied Mathematics | 2013 | 7 Pages |
Abstract
A subset SS of vertices of a graph GG is called a vertex kk-path cover if every path of order kk in GG contains at least one vertex from SS. Denote by ψk(G)ψk(G) the minimum cardinality of a vertex kk-path cover in GG. In this paper, an upper bound for ψ3ψ3 in graphs with a given average degree is presented. A lower bound for ψkψk of regular graphs is also proven. For grids, i.e. the Cartesian products of two paths, we give an asymptotically tight bound for ψkψk and the exact value for ψ3ψ3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Boštjan Brešar, Marko Jakovac, Ján Katrenič, Gabriel Semanišin, Andrej Taranenko,