On the m-eternal domination number of cactus graphs
From MaRDI portal
Publication:2330587
DOI10.1007/978-3-030-30806-3_4zbMATH Open1455.05052arXiv1907.07910OpenAlexW2972136312MaRDI QIDQ2330587FDOQ2330587
Authors: Václav Blažej, Jan Matyáš Křišt'an, T. Valla 
Publication date: 22 October 2019
Abstract: Given a graph , guards are placed on vertices of . Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional "eviction" attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.
Full work available at URL: https://arxiv.org/abs/1907.07910
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (2)
This page was built for publication: On the \(m\)-eternal domination number of cactus graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330587)
