On eternal domination and Vizing-type inequalities. Issue 3 (1st September 2020) - Driscoll, Keith; Klostermeyer, William F.; Krop, Elliot; Magnant, Colton; Taylor, Patrick
Abstract: We show sharp Vizing-type inequalities for eternal domination. Namely, we prove that for any graphs G and H, γ ∞ ( G ⊠ H ) ≥ α ( G ) γ ∞ ( 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 γ ∞ ( G □ H ) > γ ∞ ( G ) γ ∞ ( H ) where □ is the Cartesian product. For the eviction model of eternal domination, we show a sharp upper bound for e ∞ ( G ⊠ H ) .