# Bled'11 - 7th Slovenian International Conference on Graph Theory

19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

# Vertex $k$-path cover of graphs

Presented by Dr. Andrej TARANENKO
Type: Oral presentation
Track: General session

## Content

A subset $S$ of vertices of a graph $G$ is called a $k$-path vertex cover if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$. In this paper present an upper bound for $\psi_3(G)$ of graphs with given average degree. We also give a lower bound for $\psi_k(G)$ of regular graphs and some results for $\psi_k(G)$ of cartesian products of graphs. In particular, exact formulas for $\psi_3(G)$ of cartesian products of two paths are determined.

## Place

Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

More

More