On eternal domination and Vizing-type inequalities. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Driscoll, Keith; Klostermeyer, William F.; Krop, Elliot; Magnant, Colton; Taylor, Patrick
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 708
• Page End: 712
• Publication Date: 2020-09-01
• Subjects: Domination -- eternal domination -- Vizing's conjecture; 05C69
• DOI: 10.1016/j.akcej.2019.12.013
• Languages: English
• ISSNs: 0972-8600

Abstract

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 ) .