2023/05/25 by Garrison Koch, Koch, Garrison, Nathan Shank +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2305.16256
openalex publication_date 2023/05/25 · openalex created_date 2023/05/27 · openalex updated_date 2026/07/28
Given a graph G=(V,E), the dominating number of a graph is the minimum size of a vertex set, V' ⊆ V, 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:V → \0,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. We consider the k-attack Roman Domination, particularly focusing on 2-attack Roman Domination. A Roman Dominating function of G is a k-attack Roman Dominating function of G if for all j≤ k, 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 k-attack Roman Dominating number of G, \gkaRDG, is the minimum total weight over all possible k-attack Roman Dominating functions. We find \gtaRDG for particular graph class, discuss properties of k-attack Roman Domination, and make several connections with other domination ideas.