设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投稿
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
PureMathematicsnØêÆ,2023,13(6),1792-1800
PublishedOnlineJune2023inHans.https://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2023.136183
ãDomination/Ú
îîîRRRÀÀÀ
“°“‰ŒÆêƆÚOÆ§“°Üw
ÂvFϵ2023c521F¶¹^Fϵ2023c622F¶uÙFϵ2023c630F
Á‡
ã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
AdominationcoloringofagraphGissuchthateachvertexvofgraphGdominatesat
leastonecolorclass(possiblyit’sowncolorclass),andeachcolorclassisdominated
byatleastonevertexinG.Theminimumnumberofcolorsamongalldomination
coloringsiscalledthedominationchromaticnumber,denotedbyχ
dd
(G).Inthispaper,
westudythedominationcoloringofthegraphGandG
0
,whereG
0
obtainedthrough
someoperationofG.
©ÙÚ^:î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ëÏã,éuV(G)¥?¿º:vÝ^deg(v)5L«,´•ãG
¥†º:vƒº:ê8.^N(v)={u|uv∈E(G)}L«º:vm•,º:v4•^
N[v] ={u|uv∈E(G)}∪{v}5L«.XJ8ÜS¥ܺ:†V(G)¥º:vƒ,K¡º
:v››8ÜS.^P
n
ÚC
n
©OL«äkn‡º:´Ú,^mod(a,b)L«aرb¤
{ê,^[n]L«Ø‡Ln¤kê8Ü,=[n] = {1,...,n}.eãG¥íغ:vG
ëÏ ©|‡êOõ,K¡º:v´ãG•:,eG¥íØ>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š~'…Š^.CAcc
5,‘XêÆ.¢SA^FÃí2,ã/Ú¯KïÄØ2´==éã:/ÚÚ>/Ú,Ù
¦/Ú•ªƒUJÑ,'XãDominator/Ú,Dominated/Ú,Domination/Ú.l
¦ã/ÚnØïÄSN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)
þkf(u)6=f(v).ãGÚê´ãG~/Ú¤I‡ôÚ•ê8,^χ(G)L«.XJ
^k«ôÚéG?1˜‡~/ÚK´ãG˜‡k-~/Ú,^f={V
1
,V
2
,...,V
k
}L«.
¯¢þ,ãGk-~/ÚŒòãGº:8y©•k‡ôÚaV
1
,V
2
,...,V
k
,z‡ôÚa
V
i
= {v∈V(G)|f(v) = i}(i∈[k])´˜‡Õá8.
Gera <3©z[3]¥JÑãDominator /ÚVg.ãGDominator/Ú´ãG
z‡º:v–››˜‡Úa(ŒU´gÚa)˜‡~/Ú.ãGDominator Úê´ã
GDominator/Ú¤IôÚ•ê8,^χ
d
(G)L«.
BoumedieneMerouaneH<3©z[4]¥JÑãDominated/ÚVg.ãG
Dominated/Ú´•ãGz˜‡ÚaÑ–G¥˜‡º:››˜‡~/Ú.ãG
DOI:10.12677/pm.2023.1361831793nØêÆ
î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¤kDomination/Ú¥¤^ôÚê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,·‚k0±e˜‡Ún.
ÚÚÚnnn2.1[5]éuênµ
(1)en≥2,χ
dd
(P
n
) = 2·b
n
3
c+mod(n,3);
(2)en≥3,
χ
dd
(C
n
) =









2,n= 4;
3,n= 3,5;
2·b
n
3
c+mod(n,3),ÄK.
½½½nnn2.2G´˜‡ëÏã,¿…>e= uv∈E(G)Ø´•>,K
χ
dd
(G)−1 ≤χ
dd
(G−e) ≤χ
dd
(G)+1.
y²Äky²Øª†>.f=(V
1
,V
2
,···,V
k
)´íØ>ƒãG−e˜‡
Domination/Ú.e¡éãG?1/Ú.
œ/1f(u) = f(v) = i(i∈{1,2,...,k}).
‰º:u½öv/˜«#ôÚj(j/∈{1,2,...,k}).Ø”˜„5,bf(u) =j.ãG¥•
{vk/Úº:±ãG−e/Ú•ªØUC,w,ù«/Ú÷vãDomination/Ú½Â,
¤±d/Ú´ãG˜‡Domination/Ú.=χ
dd
(G)−1 ≤χ
dd
(G−e).
DOI:10.12677/pm.2023.1361831794nØêÆ
îRÀ
œ/2f(u) = i,f(v) = j(i6= j∈{1,2,...,k}).
ãG¥•{vk/Úº:±ãG−e/Ú•ªØUC,w,ù«/Ú÷vã
Domination/Ú½Â,¤±d/Ú´ãG˜‡Domination/Ú.=χ
dd
(G) ≤χ
dd
(G−e).
nþ¤ã,χ
dd
(G)−1 ≤χ
dd
(G−e).
e5y²Øªm>.f=(V
1
,V
2
,···,V
k
)´ãG˜‡Domination/Ú,…k
f(u) = m,f(v) = n(m6= n∈{1,2,...,k}).e 5éãG−e?1Domination/Ú.Œ±±en
«œ/?1?Ø.
œ/1º:vvk››ôÚaV
m
,…º:u•vk››ôÚaV
n
.
ãG−e¥¤kº:/ÚUYUìG/Ú•ª?1/Ú,w,ù«/Ú÷vã
Domination/Ú½Â,¤±d/Ú´ãG−e˜‡Domination/Ú.=χ
dd
(G−e) ≤χ
dd
(G).
œ/2º:vvk››ôÚaV
m
,´º:u››ôÚaV
n
.
eº:u´˜‡/üÚº:,KãG−e¥¤kº:UYUìG/Ú•ª?1/Ú,w
,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG−e˜‡Domination/Ú.=
χ
dd
(G−e) ≤χ
dd
(G).XJº:uØ´˜‡üÚº:,K©•±eü«œ/?1?Ø:
œ/2.13ãG−e¥,•3º:u:/Ún,K‰˜«#ôÚl(l/∈{1,2,...,k})‰
u¤k:/Ú,¿…ãG−e¥•{vk/Úº:UYUìf/Ú•ª?1/Ú,w
,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG−e˜‡Domination/Ú.=
χ
dd
(G−e) ≤χ
dd
(G)+1.
œ/2.23ãG−e¥,º:u:vk/Ún,K‰˜«#ôÚl(l/∈{1,2,...,k})‰
u?¿˜‡:/Ú,¿…ãG−e¥•{vk/Úº:Uìf/Ú•ª?1/Ú,w
,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG−e˜‡Domination/Ú.=
χ
dd
(G−e) ≤χ
dd
(G)+1.
œ/3º:v››ôÚaV
m
,º:u•››ôÚaV
n
.
XJº:u,vÑ´/üÚº:,KãG−e¥¤kº:±f/Ú•ªØC,w,
ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG−e˜‡Domination/Ú.=
χ
dd
(G−e) ≤χ
dd
(G).XJº: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¥•{vk/Úº: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¥•{vk/Úº:Uìf
/Ú•ª?1/Ú,w,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG−e˜‡
Domination/Ú.=χ
dd
(G−e) ≤χ
dd
(G)+1.
nþ¤ã,χ
dd
(G−e) ≤χ
dd
(G)+1.
~~~1½n2.2¥e.´;,‰Ñ˜‡;e.•x.ãG´ãK
3
ž,K
3
−e
∼
=
P
3
.
Kχ
dd
(K
3
)=3,χ
dd
(P
3
)=2.Ùþ.•´;,;þ.•xXã1¤«,χ
dd
(G)=3,χ
dd
(G−
DOI:10.12677/pm.2023.1361831795nØêÆ
îRÀ
e) = 2.
Figure1.AdominationcoloringofgraphsGandG−e
ã1.GÚG−e˜‡domination/Ú
½½½nnn2.3G´˜‡n(n≥2)ëÏã,¿…º:v∈V(G)Ø´•:,K
χ
dd
(G)−1 ≤χ
dd
(G−v) ≤χ
dd
(G)+deg(v)−1.
y²Äky²Øª†>.f= (V
1
,V
2
,···,V
k
)´ãG−v˜‡Domination/Ú.e
¡éãG?1/Ú.
‰º:v/˜«#ôÚj(j/∈{1,2,...,k}).ãG¥•{vk/Úº:UYUìf
/Ú•ª?1/Ú,w,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG˜‡
Domination/Ú.=χ
dd
(G)−1 ≤χ
dd
(G−v).
e5y²Øª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º:UYUì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¥•{vk/Úº:º:UYUìã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½n2.3 ¥e.´;, ‰Ñ˜‡;e.•x.ãG´ãC
10
ž, C
10
−v
∼
=
P
9
.
Kχ
dd
(C
10
) = 7,χ
dd
(P
9
) = 6.
d½n2.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.1361831796nØêÆ
îRÀ
±d/Ú´ãG˜‡Domination/Ú.džíØãG¥º:v,Œ±G−v= P
n
◦K
1
.
Ï•
χ
dd
(G) = 2+χ
dd
(P
n
) =



2d
n
3
e+1,n≡1(mod3);
2d
n
3
e+2,ÄK.
χ
dd
(P
n
◦K
1
) =









2n
3
+χ
dd
(P
n
)n≡0(mod3),
2n+1
3
+χ
dd
(P
n
)n≡1(mod3),
2n−1
3
+χ
dd
(P
n
)n≡2(mod3).
Xã2¤«´ãGDomination/Ú.¤±|χ
dd
(G)−χ
dd
(G−v)|Œ±?¿Œ.
Figure2.AdominationcoloringofgraphG
ã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´•lG¥íغ:v,¿…ò º:v¤k:ü
üƒë¤/¤ã.ãG\e´•lG¥íØ>e\\˜‡#º:x,¿…òº:x†º:u
Úv¤k:ƒë¤/¤ã.ãG
J
v´•lG¥íغ:v•¥º:ƒm>¤/¤
ã,Ùº:v¿™lãG¥íØ.Äk•Ä> :
½½½nnn3.1G´˜‡ëÏã,¿…e∈E(G),K
χ
dd
(G)−2 ≤χ
dd
(G\e) ≤χ
dd
(G)+1.
Äky²χ
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/Ú.©±en«œ/?1?Ø:
œ/1eº:uÚvÑ´üÚº:.
‰º:x/ôÚi,ãG\e•{vk/Úº:º:UYUìf/Ú•ª?1/Ú,Šâ
Domination/Ú½Â,w,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG\e˜
DOI:10.12677/pm.2023.1361831797nØêÆ
îRÀ
‡Domination/Ú.=χ
dd
(G\e) ≤χ
dd
(G)−1.
œ/2eº:u´üÚº:,º:vØ´üÚº:,¿…º:v››ÚaV
i
.
‰º:x/ôÚi,ãG\e•{vk/Úº:º:±G/Ú•ª?1/Ú,Šâ
Domination/Ú½Â,w,ù«/Ú´ãG\e˜‡Domination/Ú,Kχ
dd
(G\e) ≤χ
dd
(G).
œ/3eº:uØ´üÚº:,º:v•Ø´üÚº:,¿…º:u››ôÚaV
j
,º:v
•››ôÚaV
i
.
‰º:x/˜«#ôÚm(m/∈1,2,···,k),ãG\e•{vk/Úº:º:UYUì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•{vk/Úº:
º:UYUìG\eþf/Ú•ª?1/Ú,ŠâDomination/Ú½Â,w,ù«/Ú´ãG
˜‡Domination/Ú,Kχ
dd
(G)−2 ≤χ
dd
(G\e).
d½n2.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
.
e5•Äº: :
½½½nnn3.3G´˜‡ëÏã,¿…v∈V(G),K
χ
dd
(G)−2 ≤χ
dd
(G\v) ≤χ
dd
(G)+deg(v)−1.
Äky²χ
dd
(G\v) ≤χ
dd
(G)+deg(v)−1.f→[k]´ãG˜‡Domination/Ú,v
Ù¥˜‡:´u.e¡éãG\v?1/Ú.
ØUCº:uôÚ,^deg(v)−1«ôÚc
j
(j=1,2,···,deg(v)−1,c
j
/∈{1,2,···,k})‰
º:vm•«º:?1/Ú(Ø•¹º:u), ãG\v•{vk/Úº:º:UYUìG
þf/Ú•ª?1/Ú,w,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG\v
˜‡Domination/Ú.=χ
dd
(G\v) ≤χ
dd
(G)+deg(v)−1.
e5y²χ
dd
(G)−1 ≤χ
dd
(G\v).f→[k]´ãG\v˜‡Domination/Ú.e¡éã
G?1/Ú.
^ü«#ôÚm,n(m,n/∈{1,2,···,k})‰º:v?1/Ú,ãG¥•{vk/Úº:
º:UYUìG\vþf/Ú•ª?1/Ú,ŠâDomination/Ú½Â,w,ù«/Ú´ãG
˜‡Domination/Ú,Kχ
dd
(G)−2 ≤χ
dd
(G\v).
~~~3½n3.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½n2.3Ú½n3.3Œ±±eíØ:
DOI:10.12677/pm.2023.1361831798nØêÆ
î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.
½n3.5G´˜‡ëÏã,¿…v∈V(G),K
χ
dd
(G)−deg(v)+1 ≤χ
dd
(G
K
v) ≤χ
dd
(G)+1.
Äky²χ
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&?:
œ/1eº:v´üÚº:.
ãG
J
vº:º:UYUìGþf/Ú•ª?1/Ú,ŠâDomination/Ú½Â,
w,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG
J
v˜‡Domination/Ú.
=χ
dd
(G
J
v) ≤χ
dd
(G).
œ/2eº:º:vØ´üÚº:.
^˜«#ôÚm(m/∈1,2,···,k)‰/ôÚiº:?1/Ú,Øº:v.ãG
J
v•{
vk/Úº:º:UYUìGþf/Ú•ª?1/Ú,ŠâDomination/Ú½Â,w
,ù«/Ú÷vãDomination/Ú½Â,¤±d/Ú´ãG
J
v˜‡Domination/Ú.=
χ
dd
(G
J
v) ≤χ
dd
(G)+1.
e5y²χ
dd
(G)−deg(v)+1 ≤χ
dd
(G
J
v).f→[k]´ãG
J
v˜‡Domination/
Ú,vÙ¥˜‡:´u.e¡éãG?1/Ú.
ØUCº:uôÚ,^deg(v)−1«ôÚc
j
(j=1,2,···,deg(v)−1,c
j
/∈{1,2,···,k})é
º:vm•¥º:?1/Ú(Ø•)º:u), ãG\v•{vk/Úº:º:UYUìG
þf/Ú•ª?1/Ú,ŠâDomination/Ú½Â, w,ù«/Ú÷vãDomination /Ú
½Â,¤±d/Ú´ãG
J
v˜‡Domination/Ú.=χ
dd
(G)−deg(v)+1 ≤χ
dd
(G
J
v).
~~~4½n3.5¥e.´;,‰Ñ˜‡;e.•x.ãG´ãK
n
ž,K
n
J
v
∼
=
K
1,n
.Kχ
dd
(K
n
)=n,χ
dd
(K
1,n
)=2.Ùþ.•´;,;þ.•xXã3¤«,χ
dd
(G)=
4,χ
dd
(G
J
v) = 5.
Figure3.AdominationcoloringofgraphsGandG
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.1361831799nØêÆ
îRÀ
4.o(
©3Domination/Ú½Â†GhanbariN0˜ãöŠÄ:þ,ïÄã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°,ŸwA.Mycielskianã››XÚê[J].nØêÆ,2021,11(11):1911-
1917.https://doi.org/10.12677/PM.2021.1111213
DOI:10.12677/pm.2023.1361831800nØêÆ

版权所有：汉斯出版社 (Hans Publishers) Copyright © 2023 Hans Publishers Inc. All rights reserved.