设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
PureMathematics
n
Ø
ê
Æ
,2023,13(6),1792-1800
PublishedOnlineJune2023inHans.https://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2023.136183
ã
Domination
/Ú
îîîRRR
ÀÀÀ
“
°
“
‰
Œ
Æ
ê
Æ
†
Ú
O
Æ
§
“
°
Ü
w
Â
v
F
Ï
µ
2023
c
5
21
F
¶
¹
^
F
Ï
µ
2023
c
6
22
F
¶
u
Ù
F
Ï
µ
2023
c
6
30
F
Á
‡
ã
G
˜
‡
Domination
/Ú
´¦
ã
G
z
‡
º:
v
›
›–
˜
‡
Ú
a
(
Œ
U
´
g
Ú
a
)
§
¿
…
z
˜
‡
Ú
a
–
G
¥
˜
‡
º:
›
›
˜
‡
~
/Ú
"
ã
G
Domination
Ú
ê´
ã
G
Domination
/Ú
¤
I
•
ô
Ú
ê
8
§
^
χ
dd
(
G
)
L
«
"
©
ï
Ä
ã
G
Domination
Ú
ê
†
ã
G
Ï
L
,
«
ö
Š
ã
G
0
Domination
Ú
ê
ƒ
m
'
X
"
'
…
c
Domination
/Ú
§
Domination
Ú
ê
§
ö
Š
ã
DominationColoringofGraphs
XudongYan
CollegeofMathematicsandStatistics,QinghaiNormalUniversity,XiningQinghai
Received:May21
st
,2023;accepted:Jun.22
nd
,2023;published:Jun.30
th
,2023
Abstract
Adominationcoloringofagraph
G
issuchthateachvertex
v
ofgraph
G
dominatesat
leastonecolorclass(possiblyit’sowncolorclass),andeachcolorclassisdominated
byatleastonevertexin
G
.Theminimumnumberofcolorsamongalldomination
coloringsiscalledthedominationchromaticnumber,denotedby
χ
dd
(
G
)
.Inthispaper,
westudythedominationcoloringofthegraph
G
and
G
0
,where
G
0
obtainedthrough
someoperationof
G
.
©
Ù
Ú
^
:
îR
À
.
ã
Domination
/Ú
[J].
n
Ø
ê
Æ
,2023,13(6):1792-1800.
DOI:10.12677/pm.2023.136183
îR
À
Keywords
DominationColoring,DominationChromaticNumber,OperationsofGraph
Copyright
c
2023byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CC BY4.0).
http://creativecommons.org/licenses/by/4.0/
1.
Ú
ó
†ý
•
£
©
¤
ï
Ä
ã
þ
´
{
ü
!
Ã
•
ë
Ïã
,
˜
~
^
;
’
â
Š
Ú
Î
Ò
Œ
±
ë
•
©
z
[1,2].
G
= (
V
(
G
)
,E
(
G
))
´
˜
‡
n
ë
Ïã
,
é
u
V
(
G
)
¥
?
¿
º:
v
Ý
^
deg
(
v
)
5
L
«
,
´
•
ã
G
¥
†
º:
v
ƒ
º:
ê
8
.
^
N
(
v
)=
{
u
|
uv
∈
E
(
G
)
}
L
«
º:
v
m
•
,
º:
v
4
•^
N
[
v
] =
{
u
|
uv
∈
E
(
G
)
}∪{
v
}
5
L
«
.
X
J
8
Ü
S
¥
Ü
º:
†
V
(
G
)
¥
º:
v
ƒ
,
K
¡
º
:
v
›
›
8
Ü
S
.
^
P
n
Ú
C
n
©
OL
«
ä
k
n
‡
º:
´
Ú
,
^
mod
(
a,b
)
L
«
a
Ø
±
b
¤
{
ê
,
^
[
n
]
L
«
Ø
‡
L
n
¤
k
ê
8
Ü
,
=
[
n
] =
{
1
,...,n
}
.
e
ã
G
¥
í
Ø
º:
v
G
ë
Ï
©
|
‡
ê
O
õ
,
K
¡
º:
v
´
ã
G
•
:
,
e
G
¥
í
Ø
>
e
ã
G
ë
Ï
©
|
‡
ê
O
Œ
,
K
¡
>
e
´
ã
G
•
>
.
ã
Ø
¥
•
-
‡
!
•
¹
©
|ƒ
˜
´
ã
/Ú
¯
K
,
Ù
¥
•
¹
N
õ
š
~
Í
¶
ß
Ž
,
'
X
÷
v
˜
A
½
^
‡
e
ß
Ž
.
D
"
]
©
¢
S
¯
K
¥
Ò
^
ã
/Ú
n
Ø
(
~
X
:
Æ
ü
‘
L
¯
K
),
¿
…
ã
/Ú
n
Ø
3
ã
Ø
Ú
l
Ñ
ê
Æ
±
9
|
Ü
`
z
¥
å
X
š
~
'
…
Š
^
.
C
A
cc
5
,
‘
X
ê
Æ
.
¢
S
A^
F
Ã
í
2
,
ã
/Ú
¯
K
ï
Ä
Ø
2
´
==
é
ã
:
/Ú
Ú
>
/Ú
,
Ù
¦
/Ú
•
ª
ƒ
U
J
Ñ
,
'
X
ã
Dominator
/Ú
,Dominated
/Ú
,Domination
/Ú
.
l
¦
ã
/Ú
n
Ø
ï
Ä
S
N
5
´
L
.
ã
/Ú
n
Ø
3
¢
S
)
¹
¥
A^
´
š
~
2
•
,
'
X
ã
Domination
/Ú
3
Ñ
õ
¯
K
!
NÝ
¯
K
!
•
Á
F
§
S
ü
¯
K
!
‘
§
†
¿
S
ü
¯
K
Ú
•
á
´
»
¯
K
Ñ
å
X
š
~
-
‡
Š
^
.
ã
G
˜
‡
~
/Ú
é
Au
˜
‡
N
f
:
V
(
G
)
→
Z
+
,
¦
?
¿
ü
‡
ƒ
º:
u,v
∈
V
(
G
)
þ
k
f
(
u
)
6
=
f
(
v
).
ã
G
Ú
ê´
ã
G
~
/Ú
¤
I
‡
ô
Ú
•
ê
8
,
^
χ
(
G
)
L
«
.
X
J
^
k
«
ô
Ú
é
G
?
1
˜
‡
~
/Ú
K
´
ã
G
˜
‡
k
-
~
/Ú
,
^
f
=
{
V
1
,V
2
,...,V
k
}
L
«
.
¯¢
þ
,
ã
G
k
-
~
/Ú
Œ
ò
ã
G
º:
8
y
©
•
k
‡
ô
Ú
a
V
1
,V
2
,...,V
k
,
z
‡
ô
Ú
a
V
i
=
{
v
∈
V
(
G
)
|
f
(
v
) =
i
}
(
i
∈
[
k
])
´
˜
‡
Õ
á
8
.
Gera
<
3
©
z
[3]
¥
J
Ñ
ã
Dominator
/Ú
V
g
.
ã
G
Dominator
/Ú
´
ã
G
z
‡
º:
v
–
›
›
˜
‡
Ú
a
(
Œ
U
´
g
Ú
a
)
˜
‡
~
/Ú
.
ã
G
Dominator
Ú
ê´
ã
G
Dominator
/Ú
¤
Iô
Ú
•
ê
8
,
^
χ
d
(
G
)
L
«
.
BoumedieneMerouaneH
<
3
©
z
[4]
¥
J
Ñ
ã
Dominated
/Ú
V
g
.
ã
G
Dominated
/Ú
´
•
ã
G
z
˜
‡
Ú
a
Ñ
–
G
¥
˜
‡
º:
›
›
˜
‡
~
/Ú
.
ã
G
DOI:10.12677/pm.2023.1361831793
n
Ø
ê
Æ
îR
À
Dominated
Ú
ê´
ã
G
Dominated
/Ú
¤
Iô
Ú
•
ê
8
,
^
χ
dom
(
G
)
L
«
.
½½½
ÂÂÂ
1
[5]
ã
G
˜
‡
Domination
/Ú
´¦
ã
G
z
‡
º:
v
›
›–
˜
‡
Ú
a
(
Œ
U
´
g
Ú
a
),
¿
…
z
˜
‡
Ú
a
–
G
¥
˜
‡
º:
›
›
˜
‡
~
/Ú
.
ã
G
Domination
Ú
ê´
•
ã
G
¤
k
Domination
/Ú
¥
¤
^
ô
Ú
ê
8
•
¤
é
A
ô
Ú
ê
8
,
^
χ
dd
(
G
)
L
«
.
Kavitha.K
<
3
©
z
[6]
¥
ï
Ä
C
n
Dominator
Ú
ê
.QinChen,ChenyeZhao,
MinZhao
<
3
©
z
[7]
ï
Ä
(
k
¦
È
ã
P
n
P
m
,P
n
C
m
,C
n
C
m
Dominator
Ú
ê
.
NazaninMovarraei
<
3
©
z
[8]
ï
Ä
2
Â
Petersen
ã
Dominator
Ú
ê
.WayneGoddard,
MichaelA.Henning
<
3
©
z
[9]
ï
Ä
ä
k
†
»
²
¡
ã
Dominator
Ú
ê
.SaeidAlikhani
Ú
MohammadR.Piri
<
3
©
z
[10]
ï
Ä
õ
>
/
l
<
Ý
ã
Dominated
Ú
ê
.KlavzarS,
TavakoliM
<
3
©
z
[11]
ï
Ä
•
)
ã
Dominated
Ú
ê
.Zhou
<
3
©
z
[5]
¥
ï
Ä
´
!
!
ì
!
k
-
Ü
ã
!
(
ã
±
9
Ó
ã
Domination
Ú
ê
,
ï
Ä
χ
dd
(
H
)=
χ
(
H
)
A
«
ã
(
,
¿
…
é
u
?
¿
ã
Domination
/Ú
´
NP-
.
3
©
z
[12]
¥
CaiyunWang
ï
Ä
ã
G
†
ã
G
0
Total-Domination
Ú
ê
ƒ
m
'
X
,
ù
p
ã
G
0
´
ã
G
Ï
L
,
«
ö
Š
ã
.
©
z
[13]
¥
È
<
O
Ž
Ñ
Mycielskian
ã
›
›
Ú
ê
.
·
‚
•
é
u
?
¿
ã
Domination
/Ú
´
NP-
,
¤
±
©
&?
´
χ
dd
(
G
)
†
χ
dd
(
G
0
)
ƒ
m
'
X
,
Ù
¥
G
0
´
ã
G
Ï
L
,
«
ö
Š
(
í
Ø
º:
½
>
±
9
Â
º:
½
>
)
¤
ã
.
2.
ã
G
−
e
Ú
G
−
v
domination
Ú
ê
3
!
¥
,
·
‚
•
Ä
ã
G
−
e
Ú
G
−
v
domination
Ú
ê
.
ã
G
−
v
´
•
l
ã
G
¥
í
Ø
º:
v
†
v
ƒ
>
¤
ã
.
ã
G
−
e
´
l
ã
G
«
í
Ø
>
e
ã
.
3
!
¥
ã
G
−
e
Ú
G
−
v
domination
Ú
ê
.
.
•
y
²
e
¡
½
n
,
·
‚
k
0
±
e
˜
‡
Ú
n
.
ÚÚÚ
nnn
2.1
[5]
é
u
ê
n
µ
(1)
e
n
≥
2,
χ
dd
(
P
n
) = 2
·b
n
3
c
+
mod
(
n,
3);
(2)
e
n
≥
3,
χ
dd
(
C
n
) =
2
,n
= 4;
3
,n
= 3
,
5;
2
·b
n
3
c
+
mod
(
n,
3)
,
Ä
K
.
½½½
nnn
2.2
G
´
˜
‡
ë
Ïã
,
¿
…
>
e
=
uv
∈
E
(
G
)
Ø
´
•
>
,
K
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
y
²
Ä
k
y
²
Ø
ª
†
>
.
f
=(
V
1
,V
2
,
···
,V
k
)
´
í
Ø
>
ƒ
ã
G
−
e
˜
‡
Domination
/Ú
.
e
¡
é
ã
G
?
1
/Ú
.
œ
/
1
f
(
u
) =
f
(
v
) =
i
(
i
∈{
1
,
2
,...,k
}
).
‰
º:
u
½
ö
v
/
˜
«
#
ô
Ú
j
(
j/
∈{
1
,
2
,...,k
}
).
Ø
”
˜
„
5
,
b
f
(
u
) =
j.
ã
G
¥
•
{
v
k
/Ú
º:
±
ã
G
−
e
/Ú
•
ª
Ø
U
C
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
−
e
)
.
DOI:10.12677/pm.2023.1361831794
n
Ø
ê
Æ
îR
À
œ
/
2
f
(
u
) =
i,f
(
v
) =
j
(
i
6
=
j
∈{
1
,
2
,...,k
}
).
ã
G
¥
•
{
v
k
/Ú
º:
±
ã
G
−
e
/Ú
•
ª
Ø
U
C
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
)
≤
χ
dd
(
G
−
e
)
.
n
þ
¤
ã
,
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
−
e
)
.
e
5
y
²
Ø
ª
m
>
.
f
=(
V
1
,V
2
,
···
,V
k
)
´
ã
G
˜
‡
Domination
/Ú
,
…
k
f
(
u
) =
m,f
(
v
) =
n
(
m
6
=
n
∈{
1
,
2
,...,k
}
).
e
5
é
ã
G
−
e
?
1
Domination
/Ú
.
Œ
±±
e
n
«
œ
/
?
1
?
Ø
.
œ
/
1
º:
v
v
k
›
›
ô
Ú
a
V
m
,
…
º:
u
•
v
k
›
›
ô
Ú
a
V
n
.
ã
G
−
e
¥
¤
k
º:
/Ú
U
Y
U
ì
G
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)
.
œ
/
2
º:
v
v
k
›
›
ô
Ú
a
V
m
,
´
º:
u
›
›
ô
Ú
a
V
n
.
e
º:
u
´
˜
‡
/
ü
Ú
º:
,
K
ã
G
−
e
¥
¤
k
º:
U
Y
U
ì
G
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)
.
X
J
º:
u
Ø
´
˜
‡
ü
Ú
º:
,
K
©
•
±
e
ü
«
œ
/
?
1
?
Ø
:
œ
/
2.1
3
ã
G
−
e
¥
,
•
3
º:
u
:
/Ú
n
,
K
‰
˜
«
#
ô
Ú
l
(
l/
∈{
1
,
2
,...,k
}
)
‰
u
¤
k
:
/Ú
,
¿
…
ã
G
−
e
¥
•
{
v
k
/Ú
º:
U
Y
U
ì
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
œ
/
2.2
3
ã
G
−
e
¥
,
º:
u
:
v
k
/Ú
n
,
K
‰
˜
«
#
ô
Ú
l
(
l/
∈{
1
,
2
,...,k
}
)
‰
u
?
¿˜
‡
:
/Ú
,
¿
…
ã
G
−
e
¥
•
{
v
k
/Ú
º:
U
ì
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
œ
/
3
º:
v
›
›
ô
Ú
a
V
m
,
º:
u
•
›
›
ô
Ú
a
V
n
.
X
J
º:
u,v
Ñ
´
/
ü
Ú
º:
,
K
ã
G
−
e
¥
¤
k
º:
±
f
/Ú
•
ª
ØC
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)
.
X
J
º:
u,v
¥–
˜
‡
Ø
´
ü
Ú
º:
,
K
©
•
±
e
ü
«
œ
/
?
1
?
Ø
:
œ
/
3.1
º:
u,v
Ù
¥
˜
‡
Ø
´
ü
Ú
º:
.
Ø
”
u
´
ü
Ú
º:
,
3
ã
G
−
e
¥
,
•
3
º:
v
:
/Ú
m
,
K
‰
˜
«
#
ô
Ú
l
(
l/
∈{
1
,
2
,...,k
}
)
‰
v
?
¿˜
‡
:
/Ú
,
¿
…
ã
G
−
e
¥
•
{
v
k
/Ú
º:
U
ì
f
/
Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
œ
/
3.2
º:
u,v
Ñ
Ø
´
ü
Ú
º:
.
3
ã
G
−
e
¥
,
•
3
º:
u
:
/Ú
n
,
º:
v
:
/Ú
m
,
^
˜
«
#
ô
Ú
p
(
p/
∈
{
1
,
2
,...,k
}
)
‰
u
½
v
?
¿˜
‡
º:
?
1
/Ú
,
¿
…
ã
G
−
e
¥
•
{
v
k
/Ú
º:
U
ì
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
e
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
n
þ
¤
ã
,
χ
dd
(
G
−
e
)
≤
χ
dd
(
G
)+1
.
~~~
1
½
n
2.2
¥
e
.
´
;
,
‰
Ñ
˜
‡
;
e
.
•
x
.
ã
G
´
ã
K
3
ž
,
K
3
−
e
∼
=
P
3
.
K
χ
dd
(
K
3
)=3
,χ
dd
(
P
3
)=2
.
Ù
þ
.
•
´
;
,
;
þ
.
•
x
X
ã
1
¤
«
,
χ
dd
(
G
)=3
,χ
dd
(
G
−
DOI:10.12677/pm.2023.1361831795
n
Ø
ê
Æ
îR
À
e
) = 2
.
Figure1.
Adominationcoloringofgraphs
G
and
G
−
e
ã
1.
G
Ú
G
−
e
˜
‡
domination
/Ú
½½½
nnn
2.3
G
´
˜
‡
n
(
n
≥
2)
ë
Ïã
,
¿
…
º:
v
∈
V
(
G
)
Ø
´
•
:
,
K
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
−
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
y
²
Ä
k
y
²
Ø
ª
†
>
.
f
= (
V
1
,V
2
,
···
,V
k
)
´
ã
G
−
v
˜
‡
Domination
/Ú
.
e
¡
é
ã
G
?
1
/Ú
.
‰
º:
v
/
˜
«
#
ô
Ú
j
(
j/
∈{
1
,
2
,...,k
}
).
ã
G
¥
•
{
v
k
/Ú
º:
U
Y
U
ì
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
−
v
)
.
e
5
y
²
Ø
ª
m
>
.
f
=(
V
1
,V
2
,
···
,V
k
)
´
ã
G
˜
‡
Domination
/Ú
,
…
k
f
(
v
) =
m
(
m
∈{
1
,
2
,...,k
}
).
e
¡
é
ã
G
−
e
?
1
/Ú
.
©
±
e
ü
«
œ
/
?
1
?
Ø
:
œ
/
1
ã
G
¥
Ø
–
º:
v
/
m
Ú
.
ã
G
−
v
¥
¤
k
º:
U
Y
U
ì
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
v
)
≤
χ
dd
(
G
)
.
œ
/
2
ã
G
¥•
k
º:
v
/
m
Ú
.
^
º:
v
Ý
«
ô
Ú
c
n
(
n
=1
,
2
,
···
,k,c
n
/
∈{
1
,
2
,
···
,k
}
)
Ú
ô
Ú
i
éº:
v
m
•
¥
º:
?
1
/Ú
,
ã
G
−
v
¥
•
{
v
k
/Ú
º:º:
U
Y
U
ì
ã
G
−
v
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
−
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
−
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
Ï
L
œ
/
1
Ú
œ
/
2
Œ
•
,
χ
dd
(
G
−
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
~~~
2
½
n
2.3
¥
e
.
´
;
,
‰
Ñ
˜
‡
;
e
.
•
x
.
ã
G
´
ã
C
10
ž
,
C
10
−
v
∼
=
P
9
.
K
χ
dd
(
C
10
) = 7
,χ
dd
(
P
9
) = 6
.
d
½
n
2.2,
Œ
±
e
¡
í
Ø
:
ííí
ØØØ
2.4
n
(
n
≥
2)
ë
Ïã
G
,
÷
v
º:
v
∈
V
(
G
)
Ø
´
•
:
,
K
|
χ
dd
(
G
)
−
χ
dd
(
G
−
v
)
|
Œ
±
?
¿
Œ
.
y
²
º:
v
1
,v
2
,
···
,v
n
^
χ
dd
(
P
n
)
«
ô
Ú
?
1
/Ú
,
‰
º:
v
¤
k
:
˜
«
#
ô
Ú
χ
dd
(
P
n
)+1,
‰
º:
v
˜
«
#
ô
Ú
χ
dd
(
P
n
)+2,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
DOI:10.12677/pm.2023.1361831796
n
Ø
ê
Æ
îR
À
±
d
/Ú
´
ã
G
˜
‡
Domination
/Ú
.
d
ž
í
Ø
ã
G
¥
º:
v
,
Œ
±
G
−
v
=
P
n
◦
K
1
.
Ï
•
χ
dd
(
G
) = 2+
χ
dd
(
P
n
) =
2
d
n
3
e
+1
,n
≡
1(
mod
3);
2
d
n
3
e
+2
,
Ä
K
.
χ
dd
(
P
n
◦
K
1
) =
2
n
3
+
χ
dd
(
P
n
)
n
≡
0(
mod
3)
,
2
n
+1
3
+
χ
dd
(
P
n
)
n
≡
1(
mod
3)
,
2
n
−
1
3
+
χ
dd
(
P
n
)
n
≡
2(
mod
3)
.
X
ã
2
¤
«´
ã
G
Domination
/Ú
.
¤
±
|
χ
dd
(
G
)
−
χ
dd
(
G
−
v
)
|
Œ
±
?
¿
Œ
.
Figure2.
Adominationcoloringofgraph
G
ã
2.
G
˜
‡
domination
/Ú
e
¡
ï
Ä
é
ã
G
?
1
º:
Ú
>
Â
ã
Domination
Ú
ê
.
3.
ã
G
\
v,G
\
e
Ú
G
J
v
domination
Ú
ê
v
∈
V
(
G
)
,e
∈
E
(
G
)
,e
=
uv
,
ã
G
\
v
´
•
l
G
¥
í
Ø
º:
v
,
¿
…
ò
º:
v
¤
k
:
ü
ü
ƒ
ë
¤
/
¤
ã
.
ã
G
\
e
´
•
l
G
¥
í
Ø
>
e
\
\
˜
‡
#
º:
x
,
¿
…
ò
º:
x
†
º:
u
Ú
v
¤
k
:
ƒ
ë
¤
/
¤
ã
.
ã
G
J
v
´
•
l
G
¥
í
Ø
º:
v
•
¥
º:
ƒ
m
>
¤
/
¤
ã
,
Ù
º:
v
¿
™
l
ã
G
¥
í
Ø
.
Ä
k
•
Ä
>
Â
:
½½½
nnn
3.1
G
´
˜
‡
ë
Ïã
,
¿
…
e
∈
E
(
G
),
K
χ
dd
(
G
)
−
2
≤
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)+1
.
Ä
k
y
²
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)+1
.
f
= (
V
1
,V
2
,
···
,V
k
)
´
ã
G
˜
‡
Domination
/Ú
,
¿
…
f
(
u
) =
i,f
(
v
) =
j
(
i,j
∈{
1
,
2
,...,k
}
).
e
¡
é
ã
G
\
e
?
1
/Ú
.
©
±
e
n
«
œ
/
?
1
?
Ø
:
œ
/
1
e
º:
u
Ú
v
Ñ
´
ü
Ú
º:
.
‰
º:
x
/
ô
Ú
i
,
ã
G
\
e
•
{
v
k
/Ú
º:º:
U
Y
U
ì
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
\
e
˜
DOI:10.12677/pm.2023.1361831797
n
Ø
ê
Æ
îR
À
‡
Domination
/Ú
.
=
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)
−
1
.
œ
/
2
e
º:
u
´
ü
Ú
º:
,
º:
v
Ø
´
ü
Ú
º:
,
¿
…
º:
v
›
›
Ú
a
V
i
.
‰
º:
x
/
ô
Ú
i
,
ã
G
\
e
•
{
v
k
/Ú
º:º:
±
G
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
´
ã
G
\
e
˜
‡
Domination
/Ú
,
K
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)
.
œ
/
3
e
º:
u
Ø
´
ü
Ú
º:
,
º:
v
•
Ø
´
ü
Ú
º:
,
¿
…
º:
u
›
›
ô
Ú
a
V
j
,
º:
v
•
›
›
ô
Ú
a
V
i
.
‰
º:
x
/
˜
«
#
ô
Ú
m
(
m/
∈
1
,
2
,
···
,k
),
ã
G
\
e
•
{
v
k
/Ú
º:º:
U
Y
U
ì
G
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
´
ã
G
\
e
˜
‡
Domination
/
Ú
,
K
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)+1
.
n
þ
¤
ã
,
k
χ
dd
(
G
\
e
)
≤
χ
dd
(
G
)+1
.
e
¡
y
²
χ
dd
(
G
)
−
2
≤
χ
dd
(
G
\
e
).
f
= (
V
1
,V
2
,
···
,V
k
)
´
ã
G
\
e
˜
‡
Domination
/Ú
.
e
¡
é
ã
G
?
1
/Ú
.
^
ü
«
#ô
Ú
m,n
(
m,n/
∈
1
,
2
,
···
,k
)
éº:
u
Ú
v
?
1
/Ú
,
ã
G
•
{
v
k
/Ú
º:
º:
U
Y
U
ì
G
\
e
þ
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
´
ã
G
˜
‡
Domination
/Ú
,
K
χ
dd
(
G
)
−
2
≤
χ
dd
(
G
\
e
).
d
½
n
2.2
Ú
3.1
Œ
±
±
e
í
Ø
:
ííí
ØØØ
3.2
ã
G
´
ë
Ïã
,
¿
…
e
∈
E
(
G
)
Ø
´
•
>
,
K
χ
dd
(
G
−
e
)+
χ
dd
(
G
\
e
)
2
−
1
≤
χ
dd
(
G
)
≤
χ
dd
(
G
−
e
)+
χ
dd
(
G
\
e
)+3
2
.
e
5
•
Ä
º:
Â
:
½½½
nnn
3.3
G
´
˜
‡
ë
Ïã
,
¿
…
v
∈
V
(
G
),
K
χ
dd
(
G
)
−
2
≤
χ
dd
(
G
\
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
Ä
k
y
²
χ
dd
(
G
\
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
f
→
[
k
]
´
ã
G
˜
‡
Domination
/Ú
,
v
Ù
¥
˜
‡
:
´
u
.
e
¡
é
ã
G
\
v
?
1
/Ú
.
Ø
U
C
º:
u
ô
Ú
,
^
deg
(
v
)
−
1
«
ô
Ú
c
j
(
j
=1
,
2
,
···
,deg
(
v
)
−
1
,c
j
/
∈{
1
,
2
,
···
,k
}
)
‰
º:
v
m
•
«
º:
?
1
/Ú
(
Ø
•
¹
º:
u
),
ã
G
\
v
•
{
v
k
/Ú
º:º:
U
Y
U
ì
G
þ
f
/Ú
•
ª
?
1
/Ú
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
\
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
\
v
)
≤
χ
dd
(
G
)+
deg
(
v
)
−
1
.
e
5
y
²
χ
dd
(
G
)
−
1
≤
χ
dd
(
G
\
v
).
f
→
[
k
]
´
ã
G
\
v
˜
‡
Domination
/Ú
.
e
¡
é
ã
G
?
1
/Ú
.
^
ü
«
#ô
Ú
m,n
(
m,n/
∈{
1
,
2
,
···
,k
}
)
‰
º:
v
?
1
/Ú
,
ã
G
¥
•
{
v
k
/Ú
º:
º:
U
Y
U
ì
G
\
v
þ
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
´
ã
G
˜
‡
Domination
/Ú
,
K
χ
dd
(
G
)
−
2
≤
χ
dd
(
G
\
v
).
~~~
3
½
n
3.3
¥
e
.
´
;
,
‰
Ñ
˜
‡
;
e
.
•
x
.
ã
G
´
C
5
ž
,
C
5
\
v
∼
=
C
4
,
K
χ
dd
(
C
5
)=4
,χ
dd
(
C
4
)=2
.
Ù
þ
.
•
´
;
,
;
þ
.
•
x
,
ã
G
´
Ü
ã
K
2
,
4
ž
,
K
2
,
4
\
v
∼
=
K
5
,
K
χ
dd
(
K
5
) = 5
,χ
dd
(
K
2
,
4
) = 2
.
d
½
n
2.3
Ú
½
n
3.3
Œ
±
±
e
í
Ø
:
DOI:10.12677/pm.2023.1361831798
n
Ø
ê
Æ
îR
À
í
Ø
3.4
ë
Ïã
G
º:
v
Ø
´
•
:
,
K
χ
dd
(
G
−
v
)+
χ
dd
(
G
\
v
)
2
−
deg
(
v
)+1
≤
χ
dd
(
G
)
≤
χ
dd
(
G
−
v
)+
χ
dd
(
G
\
v
)
2
+1
.
½
n
3.5
G
´
˜
‡
ë
Ïã
,
¿
…
v
∈
V
(
G
),
K
χ
dd
(
G
)
−
deg
(
v
)+1
≤
χ
dd
(
G
K
v
)
≤
χ
dd
(
G
)+1
.
Ä
k
y
²
χ
dd
(
G
J
v
)
≤
χ
dd
(
G
)+1
.
f
= (
V
1
,V
2
,
···
,V
k
)
´
ã
G
˜
‡
Domination
/Ú
,
¿
…
f
(
v
) =
i
.
e
¡
é
ã
G
J
v
?
1
/Ú
.
Œ
±
©
±
e
ü
«
œ
/
?
1
&?
:
œ
/
1
e
º:
v
´
ü
Ú
º:
.
ã
G
J
v
º:º:
U
Y
U
ì
G
þ
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
J
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
J
v
)
≤
χ
dd
(
G
)
.
œ
/
2
e
º:º:
v
Ø
´
ü
Ú
º:
.
^
˜
«
#
ô
Ú
m
(
m/
∈
1
,
2
,
···
,k
)
‰
/
ô
Ú
i
º:
?
1
/Ú
,
Ø
º:
v
.
ã
G
J
v
•
{
v
k
/Ú
º:º:
U
Y
U
ì
G
þ
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
J
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
J
v
)
≤
χ
dd
(
G
)+1
.
e
5
y
²
χ
dd
(
G
)
−
deg
(
v
)+1
≤
χ
dd
(
G
J
v
).
f
→
[
k
]
´
ã
G
J
v
˜
‡
Domination
/
Ú
,
v
Ù
¥
˜
‡
:
´
u
.
e
¡
é
ã
G
?
1
/Ú
.
Ø
U
C
º:
u
ô
Ú
,
^
deg
(
v
)
−
1
«
ô
Ú
c
j
(
j
=1
,
2
,
···
,deg
(
v
)
−
1
,c
j
/
∈{
1
,
2
,
···
,k
}
)
é
º:
v
m
•
¥
º:
?
1
/Ú
(
Ø
•
)
º:
u
),
ã
G
\
v
•
{
v
k
/Ú
º:º:
U
Y
U
ì
G
þ
f
/Ú
•
ª
?
1
/Ú
,
Š
â
Domination
/Ú
½
Â
,
w
,
ù
«
/Ú
÷
v
ã
Domination
/Ú
½
Â
,
¤
±
d
/Ú
´
ã
G
J
v
˜
‡
Domination
/Ú
.
=
χ
dd
(
G
)
−
deg
(
v
)+1
≤
χ
dd
(
G
J
v
).
~~~
4
½
n
3.5
¥
e
.
´
;
,
‰
Ñ
˜
‡
;
e
.
•
x
.
ã
G
´
ã
K
n
ž
,
K
n
J
v
∼
=
K
1
,n
.
K
χ
dd
(
K
n
)=
n,χ
dd
(
K
1
,n
)=2
.
Ù
þ
.
•
´
;
,
;
þ
.
•
x
X
ã
3
¤
«
,
χ
dd
(
G
)=
4
,χ
dd
(
G
J
v
) = 5
.
Figure3.
Adominationcoloringofgraphs
G
and
G
J
v
ã
3.
G
Ú
G
J
v
˜
‡
domination
/Ú
í
Ø
3.6
G
´
˜
‡
ë
Ïã
,
¿
…
º:
v
∈
V
(
G
),
K
|
χ
dd
(
G
)
χ
dd
(
G
J
v
)
|
Œ
±
?
¿
Œ
.
DOI:10.12677/pm.2023.1361831799
n
Ø
ê
Æ
îR
À
4.
o
(
©
3
Domination
/Ú
½
Â
†
GhanbariN
0
˜
ã
ö
Š
Ä
:
þ
,
ï
Ä
ã
G
−
e
G
−
v
,
G
\
v,G
\
e
Ú
G
J
v
domination
Ú
ê
†
ã
G
domination
Ú
ê
ƒ
m
'
X
,
¿
…
•
x
A
‡
;
.
¤
÷
v
ã
.
ë
•
©
z
[1]Bondy,B.A.andMurty,U.S.R.(2008)GraphTheory.Springer,London.
https://doi.org/10.1007/978-1-84628-970-5
[2]Haynes,T.W.,Hedetniemt,S.T.andSlater,P.J.(1998)FundamentalsofDominationinGraph-
s.MarcelDekker,NewYork.
[3]Gera,R.,Rasmussen,C.andHorton,S.(2006)DominatorColoringsandSafeCliqueParti-
tions.
CongresNumerantium
,
181
,19-32.
[4]BoumedieneMerouane,H.,Haddad,M.,Chellali,M.andKheddouci,H.(1995) OntheDom-
inatorColoringinTrees.
DiscussionesMathematicaeGraphTheory
,
32
,677-683.
https://doi.org/10.7151/dmgt.1635
[5]Zhou,Y.andZhao,D.(2022)OnDominationColoringinGraphs.
Mathematics
,
10
,Article
998.https://doi.org/10.3390/math10060998
[6]Kavitha,K.andDavid,N.G.(2012)DominatorColoringonStarandDoubleStarGraph
Families.
InternationalJournalofComputerApplications
,
48
,22-25.
https://doi.org/10.5120/7328-0185
[7]Chen,Q.,Zhao,C.andZhao,M.(2017)DominatorColoringofCartesianProductsofPaths
and Cycles.
GraphsandCombinatorics
,
33
,73-83. https://doi.org/10.1007/s00373-016-1742-7
[8]Malaguti,E.andToth,P. (2010) A Survey on VertexColoringProblems.
InternationalTrans-
actionsinOperationalResearch
,
17
,1-34.https://doi.org/10.1111/j.1475-3995.2009.00696.x
[9]Goddard, W.andHenning, M.A.(2022)DominationandDominatorColoringinPlanarGraphs
withSmallDiameter.
DiscreteAppliedMathematics
,
313
,80-92.
https://doi.org/10.1016/j.dam.2022.02.003
[10]Alikhani,S.andPiri,M.R.(2019)OntheDominatedChromaticNumberofCertainGraphs.
arXiv:1910.02685
[11]Klavˇzar,S.and Tavakoli,M.(2021)Dominated andDominator Coloringsover(Edge) Corona
andHierarchicalProducts.
AppliedMathematicsandComputation
,
390
,Article125647.
https://doi.org/10.1016/j.amc.2020.125647
[12]
ç
.
ã
-Domination
/Ú
[J].
S
“
‰
Œ
ÆÆ
,2022,45(1):23-28.
[13]
È
,
>
ù
,
u
°
,
Ÿ
w
A
.Mycielskian
ã
›
›
X
Ú
ê
[J].
n
Ø
ê
Æ
,2021,11(11):1911-
1917.https://doi.org/10.12677/PM.2021.1111213
DOI:10.12677/pm.2023.1361831800
n
Ø
ê
Æ