On the Path Sequence of a Graph

• Authors: Sławomir Bakalarski , Jakub Zygadło
• Languages of publication: PL

Abstracts

PL

A subset S of vertices of a graph G = (V,E) is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from S. Denote by Ψk (G) the minimum cardinality of a k-path vertex cover in G and form a sequence Ψ (G) = (Ψ1 (G), Ψ2 (G), . . . , Ψ|V| (G)), called the path sequence of G. In this paper we prove necessary and sufficient conditions for two integers to appear on fixed positions in Ψ(G). A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.

Keywords

PL

k-path vertex cover, path sequence, list for small graphs

• Publisher: [unknown2]
• Journal: Schedae Informaticae
• Year: 2015
• Volume: 24

Dates

published

2015

online

06 - 07 - 2016

Contributors

author

Sławomir Bakalarski

author

Jakub Zygadło