Event calendar file
19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
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
Primary authors
- Dr. Andrej TARANENKO Faculty of Natural Sciences and Mathematics, University of Maribor
Co-authors
- Prof. Boštjan BREšAR Faculty of Natural Science and Mathematics UM
- Mr. Marko JAKOVAC Faculty of Natural Science and Mathematics UM
- Mr. Ján KATRENIč Institute of Computer Science, P.J. Šafárik University, Košice, Slovakia
- Prof. Gabriel SEMANIšIN Institute of Computer Science, P.J. Šafárik University, Košice, Slovakia
