|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|419606||683842||2013||7 صفحه PDF||سفارش دهید||دانلود رایگان|
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.
Journal: Discrete Applied Mathematics - Volume 161, Issues 13–14, September 2013, Pages 1943–1949