Results 21 to 30 of about 776,655 (324)
The 2-domination and Roman domination numbers of grid graphs
Discrete Mathematics & Theoretical Computer Science, 2019 We investigate the 2-domination number for grid graphs, that is the size of a smallest set $D$ of vertices of the grid such that each vertex of the grid belongs to $D$ or has at least two neighbours in $D$. We give a closed formula giving the 2-domination number of any $n \!\times\! m$ grid, hereby confirming the results found by Lu and Xu, and Shaheen
Michaël Rao, Alexandre Talon
openalex +7 more sources
On the Roman domination in the lexicographic product of graphs [PDF]
Discrete Applied Mathematics, 2012 A Roman dominating function of a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex with f(v)=0 is adjacent to some vertex with f(v)=2. The Roman domination number of G is the minimum of w(f)=∑v∈Vf(v) over all such functions.
Pavlič, Polona +2 more
core +5 more sources
A characterization of trees with equal Roman $\{2\}$-domination and Roman domination numbers [PDF]
Communications in Combinatorics and Optimization, 2019 Given a graph $G=(V,E)$ and a vertex $v \in V$, by $N(v)$ we represent the open neighbourhood of $v$. Let $f:V\rightarrow \{0,1,2\}$ be a function on $G$. The weight of $f$ is $\omega(f)=\sum_{v\in V}f(v)$ and let $V_i=\{v\in V \colon f(v)=i\}$, for $i=0,
Abel Cabrera Martinez, Ismael G. Yero
doaj +2 more sources
On trees with equal Roman domination and outer-independent Roman domination number [PDF]
Communications in Combinatorics and Optimization, 2019 A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) \to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$.
S. Nazari-Moghaddam, S.M. Sheikholeslami
doaj +2 more sources
On the strong Roman domination number of graphs [PDF]
Discrete Applied Mathematics, 2017 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 ...
González Yero, Ismael +4 more
core +5 more sources
Roman domination number on cardinal product of paths and cycles [PDF]
Croatian Operational Research Review, 2015 In this paper, the authors have determined certain upper and lower bounds for Roman domination numbers on cardinal products for any two graphs and some exact values for the cardinal product of paths and cycles.
Antoaneta Klobučar, Ivona Puljić
doaj +4 more sources
Discrete Mathematics, 2003 AbstractA Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V)=∑u∈Vf(u).
E. J. Cockayne +3 more
openalex +3 more sources
On the Total Version of Triple Roman Domination in Graphs
MathematicsIn this paper, we describe the study of total triple Roman domination. Total triple Roman domination is an assignment of labels from {0,1,2,3,4} to the vertices of a graph such that every vertex is protected by at least three units either on itself or ...
Juan Carlos Valenzuela-Tripodoro +3 more
doaj +3 more sources
Hop total Roman domination in graphs
AKCE International Journal of Graphs and Combinatorics, 2023 In this article, we initiate a study of hop total Roman domination defined as follows: a hop total Roman dominating function (HTRDF) on a graph [Formula: see text] is a function [Formula: see text] such that for every vertex u with f(u) = 0 there exists ...
H. Abdollahzadeh Ahangar +3 more
doaj +2 more sources
Perfect Roman Domination: Aspects of Enumeration and Parameterization
AlgorithmsPerfect Roman Dominating Functions and Unique Response Roman Dominating Functions are two ways to translate perfect code into the framework of Roman Dominating Functions.
Kevin Mann, Henning Fernau
doaj +2 more sources