On the n-attack Roman Dominating Number of a Graph

From MaRDI portal
On the $n$-attack Roman Dominating Number of a Graph




Abstract: The Roman Dominating number is a widely studied variant of the dominating number on graphs. Given a graph G=(V,E), the dominating number of a graph is the minimum size of a vertex set, V′subseteqV, so that every vertex in the graph is either in V′ or is adjacent to a vertex in V′. A Roman Dominating function of G is defined as f:Vightarrow0,1,2 such that every vertex with a label of 0 in G is adjacent to a vertex with a label of 2. The Roman Dominating number of a graph is the minimum total weight over all possible Roman Dominating functions. In this paper, we analyze a new variant: n-attack Roman Domination, particularly focusing on 2-attack Roman Domination (n=2). An n-attack Roman Dominating function of G is defined similarly to the Roman Dominating function with the additional condition that, for any jleqn, any subset S of j vertices all with label 0 must have at least j vertices with label 2 in the open neighborhood of S. The n-attack Roman Dominating number is the minimum total weight over all possible n-attack Roman Dominating functions. We introduce properties as well as an algorithm to find the 2-attack Roman Domination number. We also consider how to place dominating vertices if you are only allowed a finite number of them through the help of a python program. Finally, we discuss the 2-attack Roman Dominating number of infinite regular graphs that tile the plane. We conclude with open questions and possible ways to extend these results to the general n-attack case.














This page was built for publication: On the $n$-attack Roman Dominating Number of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438009)