2015/02/13 by M. P. Alvarez-Ruiz, M. P. Álvarez-Ruiz, Ismael G. Yero +11 · 3 citations
Computer Science · Mathematics · Social Sciences · #05C69 #Advanced Graph Theory Research #Ancient history #Bipartite graph #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #Domination analysis #FOS: Mathematics #Graph #History #Mathematics #Political Conflict and Governance #Roman Empire #Vertex (graph theory) #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1502.03933
published in arXiv (Cornell University) (Cornell University) · 23 pages
openalex publication_date 2015/02/13 · arxiv created 2015/08/01 · arxiv updated 2015/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Based on the history that the Emperor Constantine decreed that any undefended place (with no legions) of the Roman Empire must be protected by a "stronger" neighbor place (having two legions), a graph theoretical model called Roman domination in graphs was described. A Roman dominating function for a graph G=(V,E), is a function f:V→ \0,1,2\ such that every vertex v with f(v)=0 has at least a neighbor w in G for which f(w)=2. The Roman domination number of a graph is the minimum weight, ∑v∈ Vf(v), of a Roman dominating function. In this paper we initiate the study of a new parameter related to Roman domination, which we call strong Roman domination number and denote it by γStR(G). We approach the problem of a Roman domination-type defensive strategy under multiple simultaneous attacks and begin with the study of several mathematical properties of this invariant. In particular, we first show that the decision problem regarding the computation of the strong Roman domination number is NP-complete, even when restricted to bipartite graphs. We obtain several bounds on such a parameter and give some realizability results for it. Moreover, we prove that for any tree T of order n≥ 3, γStR(T)≤ 6n/7 and characterize all extremal trees.