On the minimum vertex \(k\)-path cover of trees (Q2831594)

From MaRDI portal





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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references