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
Research Projects
Organizational Units
Journal Issue
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)$.
Description
Citation
Publisher
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
EISSN
Collections