On Eternal domination and Vizing-type inequalities
No Thumbnail Available
Authors
Elliot Krop
Keith Driscoll
William F Klostermeyer
Colton R. Magnant
Patrick Taylor
Issue Date
Type
Journal Article, Professional Journal
Language
Keywords
Alternative Title
Abstract
We show sharp inequalities of Vizing-type for eternal domination. Namely, we prove that for any graphs $G$ and $H$, $\gamma^\infty(G\boxtimes H)\ge \alpha(G)\gamma^\infty(H)$, where $\gamma^\infty$ is the eternal domination function, $\alpha$ is the independence number, and $\boxtimes$ is the strong product of graphs. This addresses a question of Klostermeyer and Mynhardt. We also show some families of graphs attaining the strict inequality $\gamma^\infty(G\square H)>\gamma^\infty(G)\gamma^\infty(H)$ where $\square$ is the Cartesian product. For the eviction model of eternal domination, we show a sharp upper bound for $e^\infty(G\boxtimes H)$.