On eternal domination and Vizing-type inequalities

Abstract

We show sharp Vizing-type inequalities for eternal domination. Namely, we prove that for any graphs G and H, where is the eternal domination function, α is the independence number, and 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 where is the Cartesian product. For the eviction model of eternal domination, we show a sharp upper bound for

Keywords

• domination
• eternal domination
• vizing’s conjecture