Vertex covers in rooted product graphs

Marko Jakovac
Faculty of Natural Sciences and Mathematics, University of Maribor

PDF

Minisymposium: GRAPH PRODUCTS

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$. A lower and an upper bound for $\psi_k$ of the rooted product graphs are presented. Two characterizations are given when those bounds are attained. Moreover, $\psi_2$ and $\psi_3$ are exactly determined.

Back to all abstracts