On Eternal domination and Vizing-type inequalities
| dc.contributor.author | Elliot Krop | |
| dc.contributor.author | Keith Driscoll | |
| dc.contributor.author | William F Klostermeyer | |
| dc.contributor.author | Colton R. Magnant | |
| dc.contributor.author | Patrick Taylor | |
| dc.date.accessioned | 2024-05-21T13:41:22Z | |
| dc.date.available | 2024-05-21T13:41:22Z | |
| dc.description.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)$. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12951/1112 | |
| dc.title | On Eternal domination and Vizing-type inequalities | |
| dc.type | Journal Article, Professional Journal | |
| dcterms.bibliographicCitation | AKCE International Journal of Graphs and Combinatorics 17(3), 708-712, (April 24, 2020) |