On the minimum vertex \(k\)-path cover of trees (Q2831594)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the minimum vertex \(k\)-path cover of trees |
scientific article; zbMATH DE number 6651230
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the minimum vertex \(k\)-path cover of trees |
scientific article; zbMATH DE number 6651230 |
Statements
10 November 2016
0 references
domination
0 references
trees
0 references
On the minimum vertex \(k\)-path cover of trees (English)
0 references
A set \(S\) of vertices of a graph \(G\) is a vertex \(k\)-path cover if every \(k\)-vertex path of \(G\) contains a vertex from \(S\). It is known that if \(T\) is a tree with \(n\) vertices, then the minimum size of a vertex \(k\)-path cover of \(T\) is at most \(n/k\). The author attempts to characterize trees where this bound is tight. Unfortunately, her main result is not complete: the bound is tight for any path with \(\ell\cdot k\) vertices, however, the recursively described class of trees that is claimed to contain all trees attaining the bound does not contain any such path for \(\ell\geq 3\).
0 references