On the Total Version of Triple Roman Domination in Graphs

Academic Edi o : Bo Zhou
Recei ed: 14 Ma ch 2025
Re ised: 7 Ap il 2025
Accep ed: 8 Ap il 2025
Published: 12 Ap il 2025
Ci a ion: Valenzuela-T ipodo o, J.C.;
Ma eos-Camacho, M.A.; Ce a, M.;
Al a ez-Ruiz, M.P. On he To al
Ve sion o T iple Roman Domina ion
in G aphs. Ma hema ics 2025,13, 1277.
h ps://doi.o g/10.3390/
ma h13081277
Copy igh : © 2025 by he au ho s.
Licensee MDPI, Basel, Swi ze land.
This a icle is an open access a icle
dis ibu ed unde he e ms and
condi ions o he C ea i e Commons
A ibu ion (CC BY) license
(h ps://c ea i ecommons.o g/
licenses/by/4.0/).
A icle
On he To al Ve sion o T iple Roman Domina ion in G aphs
Juan Ca los Valenzuela-T ipodo o 1,* , Ma ia An onia Ma eos-Camacho 2, Ma in Ce a 3
and Ma ia Pila Al a ez-Ruiz 1
1Escuela Técnica Supe io de Ingenie ía de Algeci as, Uni e sidad de Cádiz, 11202 Algeci as, Spain;
pila [email p o ec ed]
2Escuela In e nacional de Doc o ado, Uni e sidad de Se illa, 41013 Se illa, Spain; [email p o ec ed]
3
Escuela Técnica Supe io de Ingenie ía Ag onómica, Uni e sidad de Se illa, 41005 Se illa, Spain; [email p o ec ed]
*Co espondence: [email p o ec ed]; Tel.: +34-956028063
Abs ac : In his pape , we desc ibe he s udy o o al iple Roman domina ion. To al
iple Roman domina ion is an assignmen o labels om
{
0,1,2,3,4
}
o he e ices o
a g aph such ha e e y e ex is p o ec ed by a leas h ee uni s ei he on i sel o i s
neighbo s while ensu ing ha none o i s neighbo s emains unp o ec ed. Fo mally, a
o al iple Roman domina ing unc ion is a unc ion
:V(G)→ {
0,1,2,3,4
}
such ha
(N[ ]) ≥ |AN( )|+
3, whe e
AN( )
deno es he se o ac i e neighbo s o e ex
, i.e.,
hose assigned a posi i e label. We in es iga e he algo i hmic complexi y o he associa ed
decision p oblem, es ablish sha p bounds ega ding g aph s uc u al pa ame e s, and
ob ain he exac alues o se e al g aph amilies.
Keywo ds: Roman domina ion; o al Roman domina ion; iple Roman domina ion; o al
iple Roman domina ion
MSC: 05C78
1. In oduc ion
This s udy in oduces a a ia ion o he Roman domina ion p oblem in g aphs. In
p e ious wo ks, we explo ed he
[k]
-Roman domina ion model, which in ol es de ending
agains single a acks ha equi e a leas
k
uni s, ocusing on he
k=
3 case. In his
wo k, we ex end he model by ensu ing ha s onge e ices, i.e., hose wi h some legion
deployed on hem, a e no isola ed.
The Roman domina ion model o igina es om Empe o Cons an ine I’s de ensi e
s a egies [
1
–
4
]. His de ensi e s a egy aimed o posi ion he smalles possible numbe
o legions ac oss he empi e while ensu ing ha each ci y housed be ween 0 and 2 le-
gions. Ci ies wi hou legions had o be adjacen o a leas one ci y wi h wo legions ha
could p o ide p o ec ion wi hou emaining unp o ec ed i sel . This was i s modeled by
Cockayne e al. [
5
] in 2004. Since hen, many a ian s ha e been s udied o enhance i s
e iciency [6–10].
This model assigns labels
{
0,1,2
}
o ci ies based on he numbe o legions. A ci y
labeled wi h 0 mus be adjacen o a ci y labeled wi h 2 o ensu e de ense wi hou lea ing
o he ci ies unp o ec ed. This de ines a Roman domina ing unc ion (RDF), and i s minimum
weigh is called he Roman domina ion numbe , γR(G).
A o al domina ing se
S
in a g aph
G
gua an ees ha any e ex has a neighbo in
S
. Liu e al. [
11
] in oduced he o al Roman domina ion numbe o g aphs wi hou isola ed
e ices, deno ed
γ R(G)
, which minimizes he weigh o an RDF, making su e ha he se
o e ices wi h a posi i e label o m a o al domina ing se .
Ma hema ics 2025,13, 1277 h ps://doi.o g/10.3390/ma h13081277
Ma hema ics 2025,13, 1277 2 o 19
The double Roman domina ion, in oduced by Beele e al. [
12
], uses labels
{
0,1,2, 3
}
,
ensu ing ha wo legions can de end each ci y. Shao e al. [
13
] and Hao e al. [
14
] ex ended
his o o al double Roman domina ion, combining bo h condi ions.
Ahanga e al. [
15
] in oduced he
[k]
-Roman domina ion model, ocusing on he
k=
3
case, called iple Roman domina ion. This assigns labels
{
0,1,
. . .
,
k+
1
}
o e ices such
ha each e ex wi h
(u)<k
sa is ies
(N[u]) ≥k+|AN(u)|
, whe e
AN(u)
s ands o
he ac i e neighbo s (neighbo s wi h a posi i e label) o
u
. The minimum weigh o such a
unc ion is he
[k]
-Roman domina ion numbe ,
γ[kR](G)
. Hajja i e al. [
16
] p o ided bounds,
including γ[3R](G)≤3n
2 o g aphs wi h δ(G)≥2.
The concep o o al domina ion can be inco po a ed in o he iple Roman domina ion
model o p e en he e being isola ed e ices among labeled ones, s eng hening he
ne wo k a he po en ial cos o highe expense.
A o al iple Roman domina ing unc ion ( 3RDF) sa is ies bo h iple Roman domi-
na ion and secu es no isola ed e ices in he induced subg aph by e ices wi h posi i e
labels. The o al iple Roman domina ion numbe ,
γ[ 3R](G)
, is he minimum weigh o
a 3RDF.
This pape in oduces he o al iple Roman domina ion model. We examine he
algo i hmic complexi y o he decision p oblem, p o ide bounds, desc ibe ex emal g aphs,
and ind exac alues o se e al g aph amilies.
The es o his pape is o ganized as ollows: Sec ion 2es ablishes he necessa y
no a ion and p elimina ies. In Sec ion 3, we p o e he NP-comple eness o he associa ed
decision p oblem, e en o bipa i e g aphs. Sec ion 4p esen s sha p bounds o he o al
iple Roman domina ion numbe in e ms o s uc u al pa ame e s like maximum deg ee
and gi h. Sec ion 5de i es exac alues o speci ic g aph amilies, including pa hs and
cycles. Finally, Sec ion 6discusses he implica ions o ou esul s and sugges s u u e
esea ch di ec ions.
2. No a ion
Th oughou his pape , we conside simple, ini e, and undi ec ed g aphs.
Le G= (V,E)
be a g aph wi h e ex se
V(G)
and edge se
E(G)
. The o de o a g aph
G
is he numbe o
e ices, deno ed by
|V(G)|
, and he size o he g aph is he numbe o edges. The deg ee
o a e ex
, deno ed
dG( )
o simply
d( )
when no con usion is possible, is he numbe
o edges inciden o
. The maximum deg ee and minimum deg ee o
G
a e deno ed by
∆(G)
and
δ(G)
, espec i ely. The neighbo hood o a e ex
in a g aph
G
is he se o all e ices
adjacen o
, deno ed by
N( )
. A e ex
is called an isola ed e ex i i has no adjacen
e ices, i.e., i i s neighbo hood is emp y,
N( ) = ∅
. The closed neighbo hood o a e ex
is deno ed by
N[ ]
, and i is de ined as
N( )∪ { }
. The induced subg aph
G[S]
o a g aph
G
is o med by a subse
S⊆V(G)
o e ices, along wi h all edges in
G
ha ha e bo h
endpoin s in
S
. A g aph is egula i all o i s e ices ha e he same deg ee, ha is, i is
k
- egula i each e ex has deg ee
k
. A uni e sal e ex in a g aph is a e ex ha is adjacen
o all o he e ices in he g aph, meaning i s deg ee is
|V(G)| −
1, whe e
|V(G)|
is he
numbe o e ices in he g aph.
Apa h
Pn
on leng h
n−
1 is a g aph wi h
n
e ices a anged in a linea sequence,
whe e each e ex (excep he endpoin s) has a deg ee o 2. A cycle
Cn
o leng h
n
is a g aph
wi h
n
e ices o ming a closed pa h, whe e each e ex has a deg ee o 2. The gi h o a
g aph is de ined as he leng h o he sho es cycle in he g aph. I no cycles exis , he gi h
is said o be in ini e. The dis ance be ween wo e ices
u
and
, deno ed by
d(u
,
)
, is he
leng h o a sho es pa h wi h end- e ices
u
and
. A se o e ices ha is a
k
-independen
se is whe e e e y pai o e ices o he se a e a a dis ance, as leas
k
. The s a g aph
S1,q
consis s o a cen al e ex adjacen o
q
lea es. A ee is a connec ed g aph con aining no
Ma hema ics 2025,13, 1277 3 o 19
cycles. A g aph is said o be connec ed i he e is a pa h be ween e e y pai o e ices. F om
now on, we e e o a non- i ial connec ed g aph as an n c-g aph. The comple e g aph
Kn
has
an edge be ween e e y pai o e ices and he comple e bipa i e g aph
Kp,q
consis s o wo
disjoin se s o e ices o o de s
p
and
q
, whe e each e ex in one se is adjacen o all
e ices in he o he se .
Alea is a e ex o deg ee one. A weak suppo e ex is a e ex adjacen o a lea ,
while a s ong suppo e ex is a e ex adjacen o a leas wo lea es.
The co ona p oduc o wo g aphs
G
and
H
, deno ed by
G◦H
, is ob ained by aking
one copy o
G
, called he cen e g aph, and a numbe o copies o
H
equal o he o de o
G
. Then, each copy o
H
is assigned a e ex in
G
, and ha one e ex is a ached o each
e ex in i s co esponding Hcopy by an edge (see Figu e 1).
Figu e 1. The co ona p oduc K4◦K2.
Rega ding domina ion in g aphs, a domina ing se ( o sho , d-se ) o
G
is a se
D⊆V(G)
such ha e e y e ex in
V(G) D
has a neighbo in
D
. The domina ion num-
be
γ(G)
is he minimum ca dinali y o a domina ing se . A
γ
-se is a domina ing se
wi h ca dinali y equal o
γ=γ(G)
. A Roman domina ing unc ion on
G
( o sho , RDF)
is a unc ion
:V(G)→ {
0,1,2
}
such ha e e y e ex wi h
( ) =
0 has a neighbo
u
wi h
(u) =
2. The Roman domina ion numbe (RDN)
γR(G)
is he minimum weigh
∑ ∈V(G) ( )
o e all such unc ions. A
[k]
-Roman domina ing unc ion (kRDF) is a unc ion
:V(G)→ {
0,1,
. . .
,
k+
1
}
sa is ying he s onge condi ion ha e e y e ex
wi h
( )<k
has a leas one neighbo
u
wi h
(N[u]) ≥k+|AN(u)|
. A o al iple Roman
domina ing unc ion ( 3RDF) is a 3RDF such ha he se o e ices wi h a posi i e label
induces an isola ed- ee subg aph. Analogously, he o al iple Roman domina ion numbe
( 3RDN) o a g aph Gis deno ed by γ[ 3R](G).
In Figu e 2, we can ind wo o al iple Roman domina ing unc ions in a g aph
G
.
We may eadily check ha he one depic ed on he igh has he minimum weigh .
All no a ion ollows he s anda d con en ions in g aph heo y.
4
2
2
2
0
3
1
0
(a) A 3RD- unc ion wi h weigh 14.
0
4
4
0
0
22
0
(b) A 3RD- unc ion wi h weigh 12.
Figu e 2. Two di e en o al iple Roman domina ing unc ions.
Ma hema ics 2025,13, 1277 4 o 19
3. Complexi y
The goal o his sec ion is o p o e ha he o al iple Roman domina ion decision
p oblem ( 3RDP) is NP-comple e e en o bipa i e g aphs.
We p o e his by showing he equi alence o any ins ance o he 3RDP wi h an
ins ance o one o he Exac 3-Co e (X3C) p oblem. Fo mally, we conside he ollowing
decision p oblems:
3RDP PROBLEM
Ins ance: G aph G= (V,E)and a posi i e in ege K.
Ques ion: Does Gha e a 3RD unc ion wi h (V)≤K?
X3C PROBLEM
Ins ance: A ini e se X,|X|=3q, and a collec ion Co 3-elemen subse s o X.
Ques ion: Does he e exis a subse
C′⊆C
such ha e e y elemen o
X
appea s in exac ly
one elemen o C′?
P oposi ion 1. 3RDP is NP-comple e o bipa i e g aphs.
P oo .
We can eadily p o e ha 3RDP is in he NP-class because any po en ial solu-
ion can be e i ied in polynomial ime. We now show ha con e ing any ins ance o
X3C o an ins ance o 3RDP esul s in equi alen solu ions o bo h p oblems. Conside
X={x1,x2, . . . , x3q}
and
C={C1
,
C2
,
. . .
,
C }
, an ins ance
(X
,
C)
o X3C. Fo each
xi∈X
,
we include a gadge
Hi
by adding wo pendan e ices
{p1
ik
,
p2
ik}
o each e ex
yik
o
k=
2,3,4 o he cycle
{yi1
,
yi2
,
yi3
,
yi4}
. Addi ionally, o each
Cj∈C
, we cons uc he gad-
ge Wjby adding wo pendan e ices {q1
jl,q2
jl} o each e ex zjl o he pa h {zj1,zj2,zj3}.
We cons uc he g aph
Γ=Γ(X
,
C)
as ollows: We s a wi h a bipa i e g aph whe e
he e ex se consis s o
X∪C
. Each
xi∈X
is adjacen o a e ex
Cj∈C
i and only i
xi
is one o he h ee elemen s belonging o he 3-elemen subse
Cj
(i.e.,
Cj={xj1
,
xj2
,
xj3}
and
xi∈ {xj1
,
xj2
,
xj3}
). We hen inco po a e he gadge s
Hi
by adding an edge be ween
xi
and
yi1
o
i=
1,
. . .
,3
q
. Simila ly, we a ach he gadge s
Wj
o
Γ
by adding edges joining
he e ices {Cj,zj1}and {Cj,zj3}, espec i ely, o j=1, . . . , (see Figu e 3).
p1
i2
p2
i2
p2
i3
p1
i3
p2
i4
p1
i4
yi3
yi4yi2
yi1
xi
x1x2xix3q
· · · · · ·
· · ·· · ·
C1C2CjC −1C
q1
j1
q2
j1
q2
j2
q1
j2
p2
j3
q1
j3
Cj
zj3zj1
zj2
Hi
Wj
Figu e 3. Gadge s a ached o xiand Cjwhen cons uc ing he bipa i e g aph Γ.
Clea ly, he cons uc ed g aph is bipa i e wi h e ex classes
{xi,yi2,yi4,p1
i3,p2
i3: 1 ≤i≤3q} ∪ {zj1,zj3,q1
j2,q2
j2: 1 ≤j≤ }
and
{yi1,yi3,p1
i2,p2
i2,p1
i4,p2
i4: 1 ≤i≤3q} ∪ {Cj,zj2,q1
j1,q2
j1,q1
j3,q2
j3: 1 ≤j≤ }.
Ma hema ics 2025,13, 1277 5 o 19
Now, assume ha he e exis s
C′⊆C
, which is an exac co e o he se
X
. Le
be a
unc ion o e he e ices o Γ, de ined as ollows: ( ) = 4 i
∈ {Cj:Cj∈C′} ∪ {yik: 1 ≤i≤3q, 2 ≤k≤4} ∪ {zjl: 1 ≤j≤ , 1 ≤l≤3}
and
( ) =
0 o he wise. Since
C′
is a solu ion o he X3C o he ins ance
(X
,
C)
, we may
deduce ha
|C′|=q
. On he o he hand,
(N[ ]) ≥ |AN( )|+
3 o all
∈V(Γ)
and he
induced subg aph by he se o e ices wi h a posi i e label has no isola ed e ices. Hence,
is a 3RD unc ion wi h w( ) = (V(Γ)) = 40q+12 .
To comple e he p oo , suppose ha
is a 3RDF wi h
(V(Γ)) ≤
40
q+
12
. Since
(yik)
a e suppo e ices and
is a 3RDF, we may assume ha
( ) =
4 o all
∈ {yik:
1
≤i≤
3
q
, 2
≤k≤
4
}
. Analogously, wi hou loss o gene ali y, we may assume ha
( ) = 4 o ∈ {zjl: 1 ≤j≤ , 1 ≤l≤3}.
I
(yi1)=
0 o some 1
≤i≤
3
q
, hen we may de ine a new unc ion
∗
as ollows:
∗(yi1) =
0,
∗(Cji) = min{ (Cji) + (yi1)
,4
}
, whe e
Cji
is a clause con aining
xi
. As he
e ex
yi1
is o al iple domina ed by any o he e ices
yik
, wi h
k=
2,3,4, we ha e
ha
∗
is a 3RDF wi h weigh a mos
(V)
. So, we may assume ha
(yi1) =
0 o all
i=1, . . . , 3q.
Analogously, i
(xi)=
0 o some 1
≤i≤
3
q
, he unc ion
∗(xi) =
0,
∗(Cji) =
min{ (Cji) + (xi)
,4
}
, whe e
Cji
is a clause con aining
xi
. Since he e ices
Cj
a e adjacen
o bo h
zjk
, wi h
k∈ {
1,3
}
, hen we ha e ha
∗
is a 3RDF wi h weigh a mos
(V)
.
Then, we may assume ha (xi) = 0 o all i=1, . . . , 3q.
In such a case, we ha e ha
(V(Γ)) =
12
+
36
q+∑1≤j≤ (Cj)≤
40
q+
12
, which
implies ha ∑1≤j≤ (Cj)≤4q.
Le
C′
be
{Cj: (Cj) =
4
}
and suppose ha
|C′|=s<q
. Then, he numbe o e ex
xi∈X
wi h a neighbo in
C′
is a mos 3
s
. As a esul ,
|xi:N(xi)∩C′=∅| ≥
3
q−
3
s
and
(N[xi]) ≥ |AN(xi)|+
3
≥
5 o each e ex
xi∈X
wi hou neighbou s in
C′
. Also, gi en
ha he ca dinali y o Cjis h ee, i mus be ha
∑
1≤j≤
(Cj) = ∑
Cj∈C′
(Cj) + ∑
Cj∈C C′
(Cj)
=4s+1
3∑
xi/∈N(C′)
(N[xi])
≥4s+5
3(3q−3s) = 5q−s>4q,
which is a con adic ion.
The e o e,
|C′|=q
wi h
( ) =
4 i
∈C′
and
( ) =
0 i
∈C C′
. As
(xi) =
0 and
(yi) =
0 o all
i
, hen he e exis
C′
ji∈C′
wi h
xi∈C′
ji
. Taking in o accoun ha
|X|=
3
q
and he ca dinali y o Cjis h ee, hen he elemen s o C′a e disjoin om each o he .
Hence, C′sol es he ins ance (X,C)o he X3C p oblem.
Al hough he p oo o he esul is leng hy, he key insigh lies in cons uc ing a bi-
pa i e g aph associa ed wi h he decision p oblem. This g aph is buil om he elemen s
xi∈X
and he clauses
Cj
(3-elemen subse s
{xj1
,
xj2
,
xj3}
), which es ablishes he equi a-
lence be ween he exis ence o a solu ion o he X3C p oblem and he exis ence o a o al
iple Roman domina ion unc ion wi h he gi en weigh .

Ma hema ics 2025,13, 1277 6 o 19
4. Bounds
Once i is shown ha calcula ing he exac alue o he o al iple Roman domina ion
numbe ( 3RDN) is NP-ha d, i is a na u al s ep o wa d o bound his pa ame e in e ms
o well-known s uc u al ea u es o a g aph.
Clea ly, he 3RDN o a disconnec ed g aph is he sum o he 3RDN o i s componen s.
As we ha e men ioned abo e, he o al e sion o his domina ion p oblem only makes
sense o isola ed e ex- ee g aphs. The e o e, since we need any unde ended e ex o
be able o ecei e a leas 3 uni s om i s ac i e neighbo s, i is s aigh o wa d o de i e a
i s uppe bound by assigning a label o 2 o each e ex in he g aph.
P oposi ion 2. Le
G
be a connec ed g aph o o de
n
. Then,
γ[ 3R](G)≤
2
n
. Equali y holds i
and only i G is he co ona p oduc H ◦K1o a connec ed g aph H wi h a K1.
P oo .
To p o e he inequali y, we conside
o be he unc ion de ined as
( ) =
2 o all
∈V(G). Clea ly, is a 3RDF and, he e o e, γ[ 3R](G)≤2n.
Nex , we cha ac e ize he g aphs ha a ain equali y.
Fi s , i
G=H◦K1
and
is a
γ[ 3R](G)
- unc ion, hen
n=|V(G)|
is an e en in ege
and
(u) + ( )≥
4 o each lea
u
, whe e
is he co esponding suppo e ex. Hence,
γ[ 3R](G) = w( )≥4n
2=2nand he equali y holds.
On he o he hand, suppose ha
γ[ 3R](G) =
2
n=
2
|V(G)|
. I
n=
2, hen
G=K2=K1◦K1
and he esul holds. So, we may assume ha
n≥
3. I
∆(G) = n−
1, hen
γ[ 3R](G)≤5, which is impossible because γ[ 3R](G) = 2n. So, assume ha ∆(G)≤n−2.
Le
be a e ex wi h maximum deg ee in
G
and deno e by
N( ) = {z1
,
. . .
,
z∆}
i s neighbo hood. Fi s , suppose ha
δ(G)≥
2. I he e exis s a e ex
w
such ha
N(w)⊆N( )
, hen conside such a e ex ha ing he minimum deg ee and deno e
by
N(w) = {zj1
,
. . .
,
zjd(w)}
i s neighbo s. Now, we may de ine a unc ion
as ollows:
( ) =
3;
(zj2) = . . . = (zjd(w)) =
0; and
(x) =
2 o he wise. By ou choice o
w
, e e y e ex labeled wi h a 2 is adjacen o a e ex wi h a posi i e label. The e -
ices wi h a label o 0 a e adjacen o bo h
and
w
; he e o e,
is a 3RDF in
G
and
γ[ 3R](G)≤w( ) =
3
+
2
(n−
1
−(d(w)−
1
)) ≤
3
+
2
(n−
1
−(
2
−
1
)) =
2
n−
1, a con a-
dic ion. I
N(w)⊆ N( )
o all
w∈V N[ ]
, hen we may de ine a unc ion
as ollows:
( ) =
3;
(z1) =
1,
(z2) = . . . = (z∆) =
0; and
(x) =
2 o he wise. We can eadily
check ha
is a 3RDF in
G
and, hence,
γ[ 3R](G)≤w( )≤
3
+
1
+
2
(n−∆(G)−
1
)≤
2n−2, again a con adic ion.
So, we can deduce ha i mus be
δ(G) =
1. I he e exis s a s ong suppo e ex
such ha
{z1
,
. . .
,
zp:p≥
2
}
a e i s lea es, hen we can de ine a unc ion
as ollows:
( ) =
4;
(z1) =
1,
(z2) = . . . = (zp) =
0; and
(x) =
2 o he wise. I is s aigh o wa d
o check ha
is a 3RDF, and hen
γ[ 3R](G)≤w( ) =
5
+
2
(n−p−
1
)≤
2
n−
1. Hence,
he e a e only weak suppo e ices in
G
. I he e exis s a e ex
∈V(G)
ha is nei he
a lea no a suppo e ex, hen we may de ine a unc ion
as ollows:
( ) =
1 and
(x) =
2 o he wise. Since
d( )≥
2, hen
is a 3RDF and
γ[ 3R](G)≤
2
n−
1, which is
no possible.
Then, e e y e ex in
G
is ei he a lea o a weak suppo e ex, which inishes he
p oo .
Ou nex esul s gi e us an uppe bound o he 3RDN in e ms o he maximum
deg ee o he g aph.
P oposi ion 3. Le
G
be an n c-g aph o o de
n
and maximum deg ee
∆(G)≥
2. Then,
γ[ 3R](G)≤3n−2∆(G).
Ma hema ics 2025,13, 1277 7 o 19
P oo .
Conside a e ex
∈V(G)
wi h maximum deg ee
∆(G)
and le
N( ) = {zj:j=
1,
. . .
,
∆(G)}
be he neighbo hood o
. Le us de ine he unc ion
:V→ {
0,1,2,3,4
}
as
ollows:
( ) =
3,
(zj) =
1 o
j=
1,
. . .
,
∆(G)
and
(u) =
3 o he emaining e ices.
Then, is 3RDF and γ[ 3R](G)≤w( ) = 3(n−∆(G)) + ∆(G) = 3n−2∆(G).
Some g aphs, including he pa h
P3
and he cycle
C3
, a ain his bound. Fu he mo e,
we can eadily e i y ha he uppe bound gi en in P oposi ion 3imp o es upon he one
p esen ed in P oposi ion 2whene e ∆(G)>n
2.
P oposi ion 4. Le
G
be an n c-g aph o o de
n
,
δ(G)≥
2, gi h
g≥
5, and maximun deg ee
∆(G)≤n−2. Then,
γ[ 3R](G)≤2(n−∆(G) + 1).
P oo .
Conside a e ex
∈V(G)
wi h maximum deg ee
∆(G)
and le
N( ) = {zj:j=
1,
. . .
,
∆(G)}
be he neighbo hood o
. Le us de ine he unc ion
:V→ {
0,1,2,3,4
}
as ollows:
( ) =
3,
(z1) =
1,
(zj) =
0 o
j=q
and
(u) =
2 o he emaining
e ices. Le
z
be any e ex belonging o
V N[ ]
. Since
δ(G)≥
2 and
g≥
5, hen
N(z)∩(V N[ ]) =∅
. The e o e, he e exis s
w∈N(z)
such ha
(w) =
2 and
(N[z]) ≥
3+|AN(z)|. Since G[V V0]has no isola ed e ices, hen is a 3RDF and
γ[ 3R](G)≤w( ) = 3+1+2(n−∆(G)−1) = 2(n−∆(G) + 1).
As shown in Table 1, hese bounds a e no compa able. The e a e g aphs o which
each bound is be e (boxed) han he o he s.
Table 1.
K−
4
s ands o a comple e g aph
K4
wi hou an edge. Bound boxed is be e han he o he s
ob ained bounds o he co esponding g aph.
Bounds C5P4◦K1K−
4
P oposi ion 210 16 8
P oposi ion 311 17 5
P oposi ion 48- -
The uppe bound can be signi ican ly imp o ed in he case o dealing wi h a egula
g aph, as demons a ed by he esul we p o e nex .
P oposi ion 5. Le
G
be an
- egula connec ed g aph o o de
n
and gi h
g≥
7. Then,
γ[ 3R](G)≤2n−2 2+3 −1.
P oo .
Le
be any e ex o he g aph
G
and le us deno e
N0={ }
,
N1=N( )
, and
N2=N(N1)−N0
. Clea ly,
|N0|=
1,
|N1|=
and
|N2|= ( −
1
)
because he gi h is a
leas 7. Conside he unc ion
:V→ {
0,1,2,3,4
}
, de ined as ollows:
( ) =
1;
(z) =
3
o all
z∈N1
;
(z) =
0 o all
z∈N2
; and
(z) =
2 o he wise. Since
≥
2 and he gi h is
g ea e han o equal o 7, we may eadily e i y ha is a 3RDF. Hence,
γ[ 3R](G)≤w( ) = 1+3 +2(n−1− − ( −1)) = 2n−2 2+3 −1.
Al hough he uppe bound ma ches he exac alue, o example, o
γ[ 3R](C7)
, i
is wo h poin ing ou ha he gi h condi ion is essen ial. I is no di icul o check
Ma hema ics 2025,13, 1277 8 o 19
ha
γ[ 3R](C5) =
8, whe eas he uppe bound gi en by P oposi ion 5would imply ha
γ[ 3R](C5)≤7.
In wha ollows, i is impo an o keep in mind ce ain condi ions ha , wi hou loss
o gene ali y, we may assume ha a γ[ 3R](G)- unc ion sa is ies.
Rema k 1. Le
be a
γ[ 3R](G)
- unc ion o an n c-g aph
G
. Le
be a suppo e ex whose lea es
a e he e ices ui, wi h i ∈ {1, . . . , }. Then,
•I is a weak suppo e ex, hen (u1)=4, ( )=0, and (u) + ( ) = 4.
•
I
is a s ong suppo e ex such ha
(wj) =
0 o all
wj∈N( ) {ui:i=
1,
. . .
,
}
,
hen we may suppose ha (u1) = 1, ( ) = 4, and (ui) = 0 o all i =1.
•
I
is a s ong suppo e ex such ha he e is a e ex
wj0∈N( ) {ui:i=
1,
. . .
,
}
wi h (wj0)=0, hen we may assume ha ( ) = 4and (ui) = 0 o all he lea es ui.
To close his sec ion, we p o e se e al esul s in which we bound he o al iple
Roman domina ion numbe o a g aph in e ms o o he domina ion pa ame e s such as
he ( o al) domina ion numbe o he o al double Roman domina ion numbe .
P oposi ion 6. Le G be an n c-g aph; hen, γ[ 3R](G)≤5γ(G).
P oo .
Le
D
be a
γ
-se and
D1⊆D
he isola ed e ices in he induced subg aph
G[D]
. Fo
each
∈D1
, we conside a e ex
˜
∈N( )
, and le us deno e
D2={˜
: ∈D1} ⊆ V D
.
Conside he unc ion
:V→ {
0,1,2,3,4
}
, de ined as ollows:
(z) =
4 o all
z∈D
;
(z) = 1 o all z∈D2; and (z) = 0 o he emaining e ices. Then,
γ[ 3R](G)≤4|D|+|D2| ≤ 4γ+|D1| ≤ 4γ+γ=5γ. (1)
This bound is me by in ini ely many g aphs, such as hose ha con ain a
uni e sal e ex.
Co olla y 1. Le G be an n c-g aph. I γ[ 3R](G) = 5γ, hen e e y γ-se is a 3-independen se .
P oo .
I
γ[ 3R](G) =
5
γ
, hen he inequali ies in (1) become equali ies. The e o e,
|D1|=γ
and all he domina ing e ices a e isola ed in
G[D]
. Since
|D2|=γ
, he e is no common
neighbo
˜
∈N( )∩N( ′)
o any pai
,
′∈D1
o dis inc e ices. Consequen ly, e e y
γ-se is a 3-independen se .
We can eadily check ha he ecip ocal is no always ue by conside ing, o example,
he cycle g aph C9, o which γ[ 3R](C9)≤14 <5γ(C9) = 15 (see Figu e 4).
1
3
0
2
2
2
03
1
Figu e 4. A o al iple Roman domina ing unc ion on C9.
Ma hema ics 2025,13, 1277 9 o 19
P oposi ion 7. Le
G
be an n c-g aph wi h a leas 3 e ices. Then,
γ (G) +
3
≤γ[ 3R](G)≤
4γ (G).
P oo .
Le
S
be a
γ
-se o
G
and le
∈S
. We can eadily p o e he uppe bound by
conside ing a unc ion
g
such ha
g(z) =
4 o all
z∈S
. This unc ion
g
is a 3RDF and,
hence, γ[ 3R](G)≤4γ (G).
Nex , we p o e he lowe bound. Assume ha
= (V0
,
V1
,
V2
,
V3
,
V4)
is a
γ[ 3R](G)
-
unc ion. Since V V0is a o al domina ing se , we ha e ha
γ (G)≤ |V1|+|V2|+|V3|+|V4|
=|V1|+2|V2|+3|V3|+4|V4|−|V2| − 2|V3| − 3|V4|
=γ[ 3R](G)− |V2| − 2|V3| − 3|V4|.
I
V4=∅
, hen
γ (G)≤γ[ 3R](G)−
3 and we a e inished. So, assume ha
V4=∅
.
I
V0=∅
, hen ei he
|V2| ≥
3,
{|V2| ≥
1,
|V3| ≥
1
}
, o
|V3| ≥
2 and, he e o e,
γ (G)≤
γ[ 3R](G)−
3. So, he only case ha emains o conside is
V0=V4=∅
. Bu , in his
si ua ion, γ (G)≤n−1<n+2≤γ[ 3R](G), which concludes he p oo .
P oposi ion 8. Le G be an n c-g aph. Then,
γ dR(G)<γ[ 3R](G)≤min5γ,3
2γ dR(G).
P oo .
Fi s , o p o e he lowe bound, conside
= (V0
,
V1
,
V2
,
V3
,
V4)
a
γ[ 3R](G)
- unc ion.
I
V4=∅
, hen
g= (V0
,
V1
,
V2
,
V3∪V4)
is a dRDF wi h weigh
w(g)≤w( )−
1 and,
hence, γ dR(G)<γ[ 3R](G).
Assume now ha
V4=∅
, which implies ha
V2∪V3=∅
. Le
∈V2∪V3
be a e ex
and conside he unc ion
g= (Vg
0
,
Vg
1
,
Vg
2
,
Vg
3)
, de ined as ollows:
g( ) = ( )−
1 and
g(z) = (z)
o he wise. Fi s , obse e ha he se
V V0
s ill o al-domina es he g aph
G
. On he o he hand, he se o ac i e neighbo s o all e ices o
V
does no change
ega dless o which unc ion,
o
g
, we conside . The e o e, i
g(u)<
2 and
u∈ N( )
,
hen
g(N[u]) = (N[u]) ≥ |AN(u)|+
3
≥ |AN(u)|+
2. I
g(u)<
2 and
u∈N( )
, hen
g(N[u]) = (N[u]) −
1
≥ |AN(u)|+
2. Hence,
g
is a dRD unc ion wi h a weigh o
w(g) = w( )−1 and γ dR(G)<γ[ 3R](G).
To p o e he uppe bound, we conside
g= (V0
,
V1
,
V2
,
V3)
a
γ dR(G)
- unc ion. Le
us de ine he ollowing unc ion:
( ) =
4 i
∈V3
;
( ) =
3 i
∈V2
; and
g(z) = (z)
o he wise. Then, is a 3RDF o Gand we may eadily deduce ha
γ[ 3R](G)≤ (V) = |V1|+3|V2|+4|V3| ≤ |V1|+3
2(2|V2|+3|V3|)
≤3
2(|V1|+2|V2|+3|V3|)=3
2γ dR(G).
This ac , and he bound gi en by P oposi ion 6, lead us o he desi ed esul .
We conclude by p o iding wo lowe bounds in e ms o he o de , maximum deg ee,
and domina ion numbe o he g aph, some o which ollow om well-known bounds o
he iple Roman domina ion numbe .
P oposi ion 9. Le G be an n c-g aph wi h n ≥3. Then, γ[ 3R](G)≥γ (G) + γ(G).
Ma hema ics 2025,13, 1277 16 o 19
To p o e ha
γ[ 3R](Pn)≥Mn
o all
n≥
13, we eason by induc ion. Le
n≥
13 be an
in ege and assume ha
γ[ 3R](Pm)≥Mm
o all 2
≤m<n
. Le us deno e
V(Pn) = {uj:
1
≤j≤n}
such ha he edges o he pa h a e
{ujuj+1}
whene e
j≤n−
1. So, we know
ha
γ[ 3R](Pn−8)≥Mn−8
and, by applying Lemma 3, we may de i e ha
γ[ 3R](Pn−5)≥
Mn−8+4. Analogously, i is deduced ha γ[ 3R](Pn−2)≥Mn−8+8=Mn−4.
Le
g
be a
γ[ 3R](Pn)
- unc ion such ha he numbe o e ices wi h a label 0 is he
minimum. By Rema k 1, we ha e ha
g(un) + g(un−1) =
4 and, wi hou loss o gene ali y,
we may suppose ha
g(un) =
1,
g(un−1) =
3. I
g(V(Pn−2)) ≥Mn−
4, hen we a e inished
because γ[ 3R](Pn) = w(g) = g(V(Pn−2)) + 1+3≥Mn.
Hence, assume ha
g(V(Pn−2)) <Mn−
4, which implies ha
g|Pn−2
is no a 3RDF
in
Pn−2
because
Mn−
4
≤Mn−2
. This may be due o se e al easons, and we mus s udy
di e en si ua ions.
Case 1:
g(un−2) = 0
. In his case, by Lemma 1, we ha e ha
g(un−3) =
2 and
g(un−4) =
2. I
g(un−5) =
1, hen we ha e o s udy wo di e en possibili ies: ei-
he
g(un−6) = 2
and
g(un−7)≥2
o
g(un−6) = 3
and
g(un−7)≥0
. In bo h cases,
we may de ine he ollowing unc ion:
g′(un−5) =
0,
g′(un−6) =
3,
g′(un−7) =
1,
g′(un−8) = min{
3,
g(un−8) + g(un−5) + g(un−6) + g(un−7)−
4
}
, and
g′(z) = g(z)
o h-
e wise. The unc ion
g′
is a 3RDF wi h he same weigh as
g
. We can p oceed simila ly
i
g(un−5) =
2 o
g(un−5) =
3. The e o e, we may assume ha
g(un) =
1,
g(un−1) =
3,
g(un−2) =
0,
g(un−3) =
2,
g(un−4) =
2,
g(un−5) =
0,
g(un−6) =
3, and
g(un−7) =
1. Since
V4=∅, hen g(un−8)≥1.
Case 1.1:
1≤g(un−8)≤2
.Then,
g(un−9)≥
2 and
g(un−8) + g(un−9)≥
4. Thus,
g|Pn−8
is a 3RDF in
Pn−8
and, consequen ly,
g(V(Pn−8)) ≥γ[ 3R](Pn−8)≥Mn−8
, implying
ha γ[ 3R](Pn) = w(g)≥Mn−8+12 =Mn.
Case 1.2:
g(un−8) = 3
.Then, we may de ine he ollowing unc ion:
g′(un−8) =
1,
g′(un−9) = min{
3,
g(un−9) +
2
}
, and
g′(z) = g(z)
o he wise. The unc ion
g′
is a 3RDF
unde he condi ions o Case 1.1.
Case 2:
g(un−2)=0
,
g(un−3) = 0
. In his case, we may de ine he unc ion
g′(un−2) =
0,
g′(un−3) = g(un−2)
, and
g′(z) = g(z)
o he wise, which is a 3RDF unde he condi ions o
Case 1.
Case 3:
g(un−2) = 1, g(un−3)=0
. Clea ly,
g(un−3)≤
2, because
g|Pn−2
is no a 3RDF
in
Pn−2
.
g(un−3) + g(un−4)≥
4, and we ha e ha
g|Pn−3
is a 3RDF in
Pn−3
, and so
γ[ 3R](Pn) = w(g) = g(V(Pn−3)) + g(un−2) + g(un−1) + g(un)≥Mn−3+5≥Mn.
Case 4:
g(un−2)≥2, g(un−3)=0
. We can de ine he unc ion
g′(un−2) =
1,
g′(un−3) =
min{
3,
g(un−3) + g(un−2)−
1
}
and
g′(z) = g(z)
o he wise, which is a 3RDF unde he
condi ions o Case 3.
Summa izing, we ha e shown ha γ[ 3R](Pn)≥Mn, which concludes he p oo .
Theo em 2. Le be n ≥3a posi i e in ege . Then,
γ[ 3R](Cn) = 


⌈3n
2⌉i n ≡0,1, 3,5,7 (mod 8).
⌈3n
2⌉+1i n ≡2,4, 6 (mod 8).
P oo . Le us deno e
Mn=


⌈3n
2⌉i n≡0,1,3,5,7 (mod 8).
⌈3n
2⌉+1 i n≡2,4,6 (mod 8).

Ma hema ics 2025,13, 1277 17 o 19
No e ha Mn=Mnwhene e n=4, 7 and Mn=Mn−1 o n∈ {4,7}.
Fi s , as shown in Figu e 5, we ha e ha
γ[ 3R](Cn)≤Mn
o
n∈ {
4,7
}
. On he o he
side, since
γ[ 3R](Cn)≤γ[ 3R](Pn)
, hen we also ha e ha
γ[ 3R](Cn)≤γ[ 3R](Pn) = Mn=
Mn o all n=4, 7.
2 2
3 0
3
1
3
0
2
0
2
Figu e 5. To al iple Roman domina ing unc ions o C4and C7.
To p o e he o he inequali y, we p oceed by induc ion on he o de o he cycle. By
P oposi ion 13, we ha e ha
γ[ 3R](Cn)≥6n
5+2=Mn o n≤8.
Le
n≥
9 be an in ege , and assume ha
γ[ 3R](Cn′)≥Mn′
o all 3
≤n′<n
.
Deno e by
V(Cn) = {u1
,
. . .
,
un}
he se o consecu i e e ices o he cycle. Le
be
a
γ[ 3R](Cn)
- unc ion such ha he numbe o e ices labeled wi h 0 is he minimum,
which, by applying Lemma 1, implies ha
V4=∅
. Since
n≥
9, we may conside i e
consecu i e e ices, say
{ui−2
,
ui−1
,
ui
,
ui+1
,
ui+2}
. By P oposi ion 2, we can assume ha
g(ui) =
0 and, again by Lemma 1, we may suppose, wi hou loss o gene ali y, ha
(ui−2) = (ui−1) =
2,
(ui+1) =
3,
(ui+2) =
1 and
(ui+3)=
0. We ha e o discuss
some di e en possibili ies.
Case 1:
(ui−3) = 0
. In his case, i mus be ha
(ui−4) =
3,
(ui−5) =
1 and
(ui−6)=
0.
Case 1.1:
(ui−6) + (ui+3)≥4
. We can eadily check ha
γ[ 3R](Cn)≥Mn
o
n=
9,10. Le
n≥
11 and conside he cycle
C′
o o de
n−
8 ob ained by joining
ui−6
and
ui+3
. Thus,
|C′
is a 3RDF and
γ[ 3R](Cn) = (V(Cn)) = (V(C′)) + (ui−5) + (ui−4) +
(ui−3) + (ui−2) + (ui−1) + (ui) + (ui+1) + (ui+2)≥M(n−8) + 12 ≥Mn.
Case 1.2:
(ui−6) = (ui+3) = 1
. Then, i mus be ha
(ui−7) = (ui+4) =
3, and
he cycle
C′
o o de
n−
8 ob ained by joining
ui−6
and
ui+3
sa is ies ha
|C′
is a 3RDF wi h
γ[ 3R](Cn) = (V(Cn)) = (V(C′)) + (ui−5) + (ui−4) + (ui−3) + (ui−2) + (ui−1) +
(ui) + (ui+1) + (ui+2)≥M(n−8) + 12 ≥Mn.
Case 1.3:
(ui−6) = 2, (ui+3) = 1
, which implies ha
(ui+4) =
3 and
(ui−7)≥
2.
I
i+
4
=i−
7, hen
n=
11 and
γ[ 3R](C11) = w( ) =
18
≥
17
=M11
. Thus, assume ha
n≥
12. I
ui+4
is adjacen o
ui−7
, hen
n=
12 and
γ[ 3R](C12) = w( )≥
20
≥
19
=M12
.
Thus, assume ha
n≥
13 and conside he cycle
C′
o o de
n−
8 ob ained by joining
ui−6
and
ui+3
. Again,
|C′
is a 3RDF wi h
γ[ 3R](Cn) = (V(Cn)) = (V(C′)) + (ui−5) +
(ui−4) + (ui−3) + (ui−2) + (ui−1) + (ui) + (ui+1) + (ui+2)≥M(n−
8
) +
12
≥
Mn.
Case 2:
(ui−3) = 1
. Then, i mus be ha
(ui−4)≥
2. Le
C′
be he cycle o o de
n−
1
ob ained by joining
ui−4
and
ui−2
. We ha e ha
γ[ 3R](Cn) = (V(Cn)) = (V(C′)) +
(ui−3)≥M(n−1) + 2≥Mn.
Case 3:
(ui−3)≥2
. I so, we may conside he cycle
C′
o o de
n−
1 ob ained by joining
ui−3
and
ui−1
. We can eadily check ha
|C′
is a 3RDF and
γ[ 3R](Cn) = (V(Cn)) =
(V(C′)) + (ui−2)≥M(n−1) + 2≥Mn.
Ma hema ics 2025,13, 1277 18 o 19
This concludes he p oo .
In his sec ion, we cha ac e ized hose g aphs wi h he minimum possible alue o
γ[ 3R](G) =
5 and p o ed ha he e a e no g aphs wi h
γ[ 3R](G) =
6. We also de e mined
he exac alues o he o al iple Roman domina ion numbe
γ[ 3R]
o pa hs and cycles.
Fo pa hs
Pn
o o de
n≥
3, we es ablished ha
γ[ 3R](Pn) = Mn
, whe e
Mn
is de ined
based on modula a i hme ic condi ions (Theo em 1). Fo cycles
Cn
, we showed ha
γ[ 3R](Cn) = ⌈3n
2⌉
when
n≡
0,1,3, 5,7
(mod
8
)
and
γ[ 3R](Cn) = ⌈3n
2⌉+
1 when
n≡
2,4,6
(mod
8
)
(Theo em 2). These esul s highligh he s uc u al di e ences be ween pa hs and
cycles and p o ide a ounda ion o u he explo a ion o his pa ame e in o he g aph
amilies.
6. Discussion
In his pape , we in oduced a no el concep called o al iple Roman domina ion in
g aphs, which ep esen s a a ian o he classical Roman domina ion p oblem by equi ing
addi ional condi ions on domina ing se s o p o ide g ea e obus ness and eliabili y o
a g aph. The new concep was o mally de ined, and i was shown ha he associa ed
decision p oblem is NP-comple e e en when es ic ed o bipa i e g aphs. Mo eo e ,
se e al sha p uppe and lowe bounds o he pa ame e we e ob ained, as well as he exac
alue o some pa icula g aphs. The o al iple Roman domina ion model has po en ial
uses in eal-wo ld scena ios equi ing laye ed de ense mechanisms, such as he below.
•
Cybe secu i y ne wo ks, whe e nodes wi h highe labels ep esen mul i-laye ed
i ewalls.
•
U ban planning, ensu ing backup esou ces (e.g., hospi als, police s a ions) a e op i-
mally placed.
• Robus senso co e age in IoT sys ems, minimizing blind spo s.
As a u u e line o esea ch, we in end o p o e ha he p oblem emains NP-comple e
in gene al bu can be educed o a linea p oblem in speci ic amilies o g aphs, such as ees.
Addi ionally, he exac alue o he pa ame e should be in es iga ed o o he g aphs o
g aph amilies wi h speci ic s uc u al p ope ies.
Au ho Con ibu ions: Concep ualiza ion, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; me hodology,
J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; alida ion, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; in es i-
ga ion, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; w i ing— e iew and edi ing, J.C.V.-T., M.A.M.-C.,
M.C. and M.P.A.-R. All au ho s ha e ead and ag eed o he published e sion o he manusc ip .
Funding: J.C. Valenzuela-T ipodo o was pa ially suppo ed by he Spanish Minis y o Science and
Inno a ion h ough he g an PID2022-139543OB-C41.
Da a A ailabili y S a emen : No new da a we e c ea ed.
Con lic s o In e es : The au ho s decla e no con lic s o in e es .
Re e ences
1. A quilla, J.; F ed icksen, H. G aphing an Op imal G and S a egy. Mil. Ope . Res..1995,1, 3–17. [C ossRe ]
2. ReVelle, C.S. Can you p o ec he Roman Empi e. Johns Hopkins Mag. 1997,49, 40.
3.
ReVelle, C.S.; Rosing, K.E. De endens impe ium omanum: A classical p oblem in mili a y s a egy. Am. Ma h. Mon. 2000,107,
585–594. [C ossRe ]
4. S ewa , I. De end he Roman Empi e! Sci. Am. 1999,281, 136–139. [C ossRe ]
5.
Cockayne, E.J.; D eye , P.A.; Hede niemi, S.M.; Hede niemi, S.T. Roman domina ion in g aphs. Disc e . Ma h. 2004,278, 11–22.
[C ossRe ]
6.
Chellali, M.; Haynes, T.W.; Hede niemi, S.T. Bounds on weak oman and 2- ainbow domina ion numbe s. Disc e . Appl. Ma h..
2014,178, 27–32. [C ossRe ]
Ma hema ics 2025,13, 1277 19 o 19
7.
Cockayne, E.J.; Fa a on, O.; Mynha d , C.M. Secu e domina ion, weak Roman domina ion and o bidden subg aphs. Bull. Ins .
Comb. I s Appl. 2003,39, 87–100.
8.
Klos e meye , W.F.; Mynha d , C.M. Secu e domina ion and secu e o al domina ion in g aphs. Discuss. Ma h. G aph Theo y.2008,
28, 267–284. [C ossRe ]
9.
Val eny, M.; Pé ez-Rosés, H.; Rod íguez-Velázquez, J.A. On he weak Roman domina ion numbe o lexicog aphic p oduc
g aphs. Disc e . Appl. Ma h. 2019,263, 257–270. [C ossRe ]
10.
Val eny, M.; Rod íguez-Velázquez, J.A. P o ec ion o g aphs wi h emphasis on ca esian p oduc g aphs. Filoma 2019,33, 319–333.
[C ossRe ]
11. Liu, C.H.; Chang, G.J. Roman domina ion on s ongly cho dal g aphs. J. Comb. Op im. 2013,26, 608–619. [C ossRe ]
12. Beele , R.A.; Haynes, T.W.; Hede niemi, S.T. Double Roman domina ion. Disc e . Appl. Ma h. 2016,211, 23–29. [C ossRe ]
13.
Shao, Z.; Amjadi, J.; Sheikholeslami, S.M.; Valina az, M. On he To al Double Roman Domina ion. IEEE Access 2019,7, 52035–52041.
[C ossRe ]
14.
Hao, G.; Volkmann, L.; Mojdeh, D.A. To al double Roman domina ion in g aphs. Commun. Comb. Op im. 2020,5, 27–39. [C ossRe ]
15.
Abdollahzadeh Ahanga , H.; Ál a ez Ruiz, M.P.; Chellali, M.; Sheikholeslami, S.M.; Valenzuela-T ipodo o, J.C. T iple Roman
domina ion in g aphs. Appl. Ma h. Compu . 2021,391, 125444. [C ossRe ]
16.
Hajja i, M.; Abdollahzadeh Ahanga , H.; Khoeila , R.; Shao, Z.; Sheikholeslami, S.M. An uppe bound on iple Roman domina ion.
Commun. Comb. Op im. 2023,8, 505–511. [C ossRe ]
17.
Valenzuela-T ipodo o, J.C.; Ma eos-Camacho, M.A.; Ce a, M.; Ál a ez-Ruiz, M.P. Fu he esul s on he [k]-Roman domina ion in
G aphs. Bull. I an. Ma h. Soc. 2024,50, 27. [C ossRe ]
Disclaime /Publishe ’s No e: The s a emen s, opinions and da a con ained in all publica ions a e solely hose o he indi idual
au ho (s) and con ibu o (s) and no o MDPI and/o he edi o (s). MDPI and/o he edi o (s) disclaim esponsibili y o any inju y o
people o p ope y esul ing om any ideas, me hods, ins uc ions o p oduc s e e ed o in he con en .