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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
PureMathematicsnØêÆ,2021,11(11),1911-1917
PublishedOnlineNovemb er2021inHans.http://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2021.1111213
Mycielskianã››XÚê
ÈÈÈ
1∗
§§§>>>ùùù
1†
§§§uuu°°°
2
§§§ŸŸŸwwwAAA
1
1
#õ“‰ŒÆêƉÆÆ§#õ¿°7à
2
#õŒÆêƆXÚ‰ÆÆ§#õ¿°7à
ÂvFϵ2021c1016F¶¹^Fϵ2021c1116F¶uÙFϵ2021c1124F
Á‡
-ãG=(V,E)´˜‡k•{üë ÏÕã"ãG››XÚ´G˜‡~:XÚ§¦
ãG¥z‡º:m+•–•¹˜«ôÚa§…z‡ôÚa–˜‡º:¤››"ãG
››XÚê´Ù››XÚ¥¤¦^•ôÚê§ P•χ
td
(G)"©Äk|^?¿ãG
››XÚê‰ÑãGMycielskianã››XÚêþ!e.¶?‰Ñ˜AÏãa
Mycielskianã››XÚê(ƒŠ"
'…c
››XÚ§››ŽXÚê§Mycielskianã
TheTotalDominationChromatic
NumbersofMycielskianGraphs
XueYang
1∗
,HongBian
1†
,HaizhengYu
2
,LinaWei
1
1
Scho olofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Oct.16
th
,2021;accepted:Nov.16
th
,2021;published:Nov.24
th
,2021
∗1˜Šö"
†ÏÕŠö"
©ÙÚ^:È,>ù,u°,ŸwA.Mycielskianã››XÚê[J].nØêÆ,2021,11(11):1911-1917.
DOI:10.12677/pm.2021.1111213
È
Abstract
LetG=(V,E)beasimple,connected,finiteandundirectedgraph.Atotaldomina-
tioncoloringofagraphGisapropercoloringofGinwhichopenneighbourhoodof
eachvertexcontainsatleastonecolorclassandeachcolorclassisdominatedbyat
leastonevertex.ThetotaldominationchromaticnumberofG,denotedbyχ
td
(G),
istheminimumnumberofcolorsrequiredforatotaldominationcoloringofG.In
thispaper,wepresenttheupperandlowerboundsoftotaldominationchromatic
numbersofMycielskiangraphofarbitrarilygraph,andobtainexactlyvaluesofthe
totaldominationchromaticnumbersofMycielskiangraphsofsomespecialgraphs.
Keywords
TotalDominationColoring,TotalDominationChromaticNumber,
MycielskianGraphs
Copyright
c
2021byauthor(s)andHansPublishersInc.
ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.0
©¥¤•ÄãÑ´k•!{üëÏã.-G=(V,E)´˜‡{ üã.ãG?˜º:v
m+•´†:vƒ:8Ü,P•N
G
(v).aq/,ãG?˜º:v4+•´:vÚ†:v
ƒ:8Ü,P•N
G
[v],…N
G
[v]=N
G
(v)∪{v}.²wwÑN
G
[v]?˜f8Ñ:v¤››.
n‡:´!©OP•P
n
,C
n
,n+1‡:(ãP•S
n
.Óã´˜‡:ê•n+1,>ê
•2n{üã,P•W
n
,§´ÏLòC
n
z‡ º:†˜‡Üº:ƒëã.÷ã´Ó
ãW
n
íÙC
n
þ˜^>ã,P•F
n
.lÇã´˜‡:ê•2n+1,>ê•3n{ü
ã,P•F
n
,§´k˜‡úº:n‡n/¤|¤ã.G“LãGÖã.
ãXÚ•´ãØ¥˜‡kïÄ+•.3ãXÚ¥,Šâýk½Â˜^‡‰ã:!
>½üöÓžXÚ.3ãG˜‡~:XÚ¥,éº:?1XÚ,¦ƒº:ØÓôÚ,
¦ãGƒº:pÉôÚXÚ¤I•ôÚê¡•ãG:XÚê,P•χ(G).ãG
¥¤käkƒÓôÚº:8Ü¡•ãGôÚa.3©¥,^iL«˜‡º:ôÚ,^V
i
DOI:10.12677/pm.2021.11112131912nØêÆ
È
L«ôÚa,V
i
´äkôÚi:8Ü.lã››5Ÿéã?1XÚkõ«•{,•kk´ã
››öXÚ,ù‡½Â´dGera<[1]32006cÄgJÑ.ãG››öX Ú´˜‡~:
XÚ¦ãGz‡º:››–˜‡ôÚa.ãG››öXÚê´Ù¤k››öXÚ¥¦^
•ôÚê,P•χ
d
(G).Ùg,2015c,Kazemi<[2]0¿ïÄã››öXÚ.ãG
››öXÚ´˜‡~:XÚ,éuãG?˜º:v,¦Øv:¤XôÚaƒ,:v
„››–˜‡ôÚa.†óƒ,››öXÚ´ã˜‡››öXÚ¦ã?˜º:v››
ôÚa´:vm+•N
G
(v)f8.ãG››öXÚê,P•χ
t
d
(G),L«ãG¤k››
öXÚ¥¦^•ôÚê.2019c,ZhuoÚZhao[3]ïÄã››XÚ.ã››XÚ´˜‡
››öXÚ,…÷vz‡ôÚa–˜‡:¤››.a q/,ã››XÚê´Ù››XÚ¥¤
¦^•ôÚê,^χ
dd
(G)L«.2021c,Chithra<[4]Äg0ã››XÚ.ãG
››XÚ´ãG˜‡››XÚ¦ãG?˜º:v››ôÚa´:vm+•N
G
(v)
f8.ãG››XÚê´¤k››XÚ¥¤¦^•ôÚê,P•χ
td
(G).Chithra
<[4]ïÄ˜AÏãa››XÚê,X:´P
n
,´ÖãP
n
,C
n
ÚÖãC
n
.
Mycielskian[5]u1995cJÑ˜«kãC†,dãG²L˜«C†˜‡#ã,¡
ƒ•ãGMycielskianã,P•µ(G).½ÂXe:-V(G)={v
1
,v
2
,···,v
n
}•ãGº:8,
V
0
(G)={x
1
,x
2
,···,x
n
}´ãGº:8éA€:8,Ù¥x
i
´v
i
€:(1≤i≤n),u
¡•µ(G)Š:.Mycielskianãº:´V(µ(G))=V(G)∪V
0
(G)∪{u},>8•E(µ(G))=
E(G)∪{v
i
x
j
|v
i
v
j
∈E(G),1≤i≤n}∪{x
i
u|x
i
∈V
0
(G),1≤i≤n}.ef´ãG˜‡››X
Ú¦^V
1
,V
2
,···,V
t
‡ôÚa,¦?˜‡ôÚaV
i
¥z‡º:ÑXôÚi(1≤i≤t),{
¤f=(V
1
,V
2
,···,V
t
).3©¥,ãGº:8€:8V
0
(G){¤X,Š:8Ü{u}{
¤U.
©Äk|^?¿ãG››XÚê‰ÑãGMycielskianã››XÚêþ!e
.;?‰Ñ˜AÏãaMycielskianã››XÚê(ƒŠ.
2.̇(J
‰½˜‡ãG,e®•ãG››XÚê,KŒãGMycielskianã››XÚê
þ!e..
½n2.1‰½?˜ãG,δ(G)≥1,Ù››XÚê•χ
td
(G),Kχ
td
(G)+1≤χ
td
(µ(G))≤
χ
td
(G)+2.
y²bχ
td
(G)=t.-f=(V
1
,V
2
,···,V
t
)´ãG˜‡››XÚ.Äk•ÄG
Mycielskianãµ(G)››XÚêþ..²w/,g=(V
1
,V
2
,···,V
t
,X,U)´ãµ(G)
˜‡››XÚ,Kχ
td
(µ(G))≤χ
td
(G)+2.2?Øãµ(G)››XÚêe..3ãµ(G)¥
º:um+•´N
µ(G)
(u)=X,Šâ››XÚ½Â7,k˜‡ º:x
i
∈XX#ôÚ¦:u
››ù‡ôÚa.Ïdχ
td
(µ(G))≥χ
td
(G)+1,y.2
e©‰½˜AÏãaMycielskianã››XÚê(ƒŠ.ÄkdChithra<3©
z[4]¥´››XÚêŒ´Mycielskianã››XÚê.
Ún2.2 [4]n≥3ž,χ
td
(P
n
)=2d
n
3
e.
DOI:10.12677/pm.2021.11112131913nØêÆ
È
½n2.3 n≥3ž,
χ
td
(µ(P
n
))=
(
2d
n
3
e+1,n≡1(mod3)ž,
2d
n
3
e+2,Ù§.
y²{v
i
|1≤i≤n}´´P
n
:8,{v
i
v
i+1
|1≤i≤n−1}´´P
n
>8.d½n2.1ÚÚ
n2.2Œχ
td
(µ(P
n
))≥2d
n
3
e+1.©±eü«œ/?Ø´Mycielskianã››XÚêþ.:
œ/1 n≡1(mod3)
n=4ž,χ
td
(µ(P
4
))≥2d
4
3
e+1=5.ãµ(P
4
)››XÚ¦^5‡ôÚ(Xã1¤«),
χ
td
(µ(P
4
))=5.dÚn2.2Œχ
td
(µ(P
4
))=χ
td
(P
4
)+1.
Figure1.Thetotaldominationcoloringofµ(P
4
)
ã1.µ(P
4
)››XÚ
n≥7ž,-n=3t+1.dÚn2.2•χ
td
(P
n
)=2d
3t+1
3
e=2t+2,f
1
=(V
1
,V
2
,···,V
2t−1
,
V
2t
,V
2t+1
,V
2t+2
)´ãP
n
˜‡››XÚ÷v:v
n−3
,v
n−2
,v
n−1
,v
n
©OXôÚ•2t−1,2t,2t+
1,2t+2,Kg
1
=(V
1
,V
2
,···,V
2t−1
,V
2t
,V
2t+1
,V
2t+2
∪U,X)´ãµ(P
n
)˜‡››XÚ…¦^
2t+3‡ôÚ,Ïdχ
td
(µ(P
n
))≤2t+3,χ
td
(µ(P
n
))≤χ
td
(P
n
)+1.
œ/2 n≡0,2(mod3)
d½n2.1Œ•χ
td
(µ(P
n
))≤2d
n
3
e+2.‡yχ
td
(µ(P
n
))=2d
n
3
e+2,•Iyχ
td
(µ(P
n
))6=
2d
n
3
e+1.
bχ
td
(µ(P
n
))=2d
n
3
e+1.´••3˜‡:x
i
∈XX#ôÚ2d
n
3
e+1,@oãµ(P
n
)Š
:u7X,˜‡ôÚl(1≤l≤2d
n
3
e).3ù«œ/e,•3˜:v k››?Û˜‡ôÚa,gñ.
χ
td
(µ(P
n
))≥2d
n
3
e+2,y.2
e¡Ún´Chithra<3©z[4]¥‰››XÚê.
Ún2.4 [4]n≥5…n6=7ž,χ
td
(C
n
)=2d
n
3
e.
n=3ž,χ
td
(C
3
)=3,ÙMycielskianãµ(C
3
)˜‡››XÚ„ã2(a),Œχ
td
(µ(C
3
))=
4.n=4ž,χ
td
(C
4
)=2,Mycielskianãµ(C
4
)˜‡››XÚ„ã2(b),Kχ
td
(µ(C
4
))≤4.
DOI:10.12677/pm.2021.11112131914nØêÆ
È
w,χ
td
(µ(C
4
))6=3,¯¢þ,χ
td
(µ(C
4
))6=3ž7k˜‡:vk››?˜ôÚa,χ
td
(µ(C
4
))≥
4,lχ
td
(µ(C
4
))≤4.n≥5ž,e¡½n‰Ñãµ(C
n
)››XÚê.
Figure2.(a)Thetotaldominationcoloringofµ(C
3
);(b)Thetotal
dominationcoloringofµ(C
4
)
ã2.(a)µ(C
3
)››XÚ;(b)µ(C
4
)››XÚ
½n2.5 n≥5ž,
χ
td
(µ(C
n
))=
(
2d
n
3
e+2,n≡0(mod3)ž,
2d
n
3
e+1,Ù§.
y²{v
i
|1≤i≤n}´C
n
:8,{v
i
v
i+1
|1≤i≤n−1}∪{v
n
v
1
}´C
n
>8.d½n2.1
ÚÚn2.4•χ
td
(µ(P
n
))≥2d
n
3
e+1.y•ÄMycielskianã››XÚêþ.,©•±e
œ/:
œ/1 n≡1(mod3)ž,-n=3t+1.ãC
n
››XÚf
1
Xe:
f
1
(v
i
)=
(
2l−1,i=3l−2½i=3lž,
2l,i=3l−2ž.
Ù¥1≤l≤t−1,2-f
1
(v
n−3
)=2t−1,f(v
n−2
)=2t,f(v
n−1
)=2t+1,Úf(v
n
)=2t+
2.´•f
1
=(V
1
,V
2
,···,V
2t−1
,V
2t
,V
2t+1
,V
2t+2
)´ãC
n
˜‡››XÚ,Kg
1
=(V
1
,V
2
∪
U,···,V
2t−1
,V
2t
,V
2t+1
,V
2t+2
,X)´ãµ(C
n
)˜‡››XÚ¦^2t+3‡ôÚ,Ïdχ
td
(µ(C
n
))≤
2d
n
3
e+1.n≡1(mod3)ž,χ
td
(µ(C
n
))=2d
n
3
e+1.
œ/2 n≡2(mod3)ž,n=3t+2.ãC
n
››XÚf
2
Xe:
f
2
(v
i
)=
(
2l−1,i=3l−2½i=3lž,
2l,i=3l−2ž.
Ù¥1≤l≤t,2-f
1
(v
n−1
)=2 t+1,f(v
n
)=2 t+2.w,f
2
=(V
1
,V
2
,···,V
2t
,V
2t+1
,V
2t+2
)´
DOI:10.12677/pm.2021.11112131915nØêÆ
È
ãC
n
˜‡››XÚ,@og
2
=(V
1
,V
2
∪U,···,V
2t+1
,V
2t+2
,X)•´ãµ(C
n
)˜‡ ››X
Ú…¦^2t+3‡ôÚ.aq/,n≡2(mod3)ž,χ
td
(µ(C
n
))=2d
n
3
e+1.
œ/3d½n2.1Œ•χ
td
(µ(C
n
))≤2d
n
3
e+2.‡yχ
td
(µ(C
n
))=2d
n
3
e+2,•Iyχ
td
(µ(C
n
))6=
2d
n
3
e+1.^½n2.3y²•{aqŒχ
td
(µ(C
n
))=2d
n
3
e+1´ØŒU,χ
td
(µ(C
n
))=
2d
n
3
e+2,y.2
e5•Ä(ãS
n
Mycielskianã››XÚê.(ã:8Ú>8©OP•V(S
n
)=
{v}∪{v
i
|1≤i≤n},E(S
n
)={vv
i
|1≤i≤n}.w,(ã››XÚê´2,e¡½n‰Ñ
ãµ(S
n
)››XÚê(ƒŠ.
½n2.6 n≥2ž,χ
td
(µ(S
n
))=4.
y²Ò(ãó,Ø”˜„5,:vXôÚ1,:v
i
XôÚ2,Kf=(V
1
,V
2
)´(ã˜‡
››XÚ.d½n2.1Œ•3≤χ
td
(µ(S
n
))≤4.•yχ
td
(µ(S
n
))=4,•Iyχ
td
(µ(S
n
))6=3.b
χ
td
(µ(S
n
))=3,©±eœ/?ØÙ››XÚ:
œ/13ãµ(S
n
)¥,S
n
¤k€:X#ôÚ3,Š:uXôÚ1½2.Š:uXôÚ1ž,
:v
i
(1≤i≤n)vk››ôÚa;Š:uXôÚ2ž,:vvk››ôÚa,gñ.
œ/2 :v
i
€:x
i
X#ôÚ2,:v€:xXôÚ3,:u•UXôÚ1,:xvk
››?˜ôÚa,gñ.
œ/3:v
i
€:x
i
X#ôÚ3,:v€:xXôÚ1,:u•UXôÚ2,:x
i
(1≤
i≤n)vk››?˜ôÚa,gñ.
Ïdχ
td
(µ(S
n
))=3´ØŒU,y.2
e¡•Äãµ(W
n
)››XÚê,Chithra[4]‰ÑÓã››XÚê(ƒŠ,3dÄ
:þ,½n2.8‰Ñãµ(W
n
)››XÚê(ƒŠ.
Ún2.7 [4]n≥3ž,
χ
td
(W
n
)=
(
3,n´óêž,
4,n´Ûêž.
½n2.8 n≥3ž,
χ
td
(µ(W
n
))=
(
4,n´óêž,
5,n´Ûêž.
y²Óã:8Ú>8©OP•V(W
n
)={v}∪{v
i
|1≤i≤n},E(W
n
)={vv
i
|1≤i≤
n}∪{v
i
v
i+1
|1≤i≤n}∪{v
n
v
1
}.w,Óã~:XÚ•´˜‡››XÚ.Ø”˜„5,n´
óêž,:vXôÚ1,:v
i
(i´Ûê)XôÚ2,:v
i
(i´óê)XôÚ3,Œ•f
1
=(V
1
,V
2
,V
3
)´Ó
ãW
n
˜‡››XÚ…¦^•ôÚê,Kg
1
=(V
1
,V
2
∪U,V
3
,X)´ãµ(W
n
)˜‡›
›XÚ¦^4‡ôÚ,χ
td
(µ(W
n
))≤4.d½n2.1•,n´óêž,χ
td
(µ(W
n
))=4.aq/,
n´Ûêž,f
2
=(V
1
,V
2
,V
3
,V
4
)´ÓãW
n
˜‡››XÚ…¦^•ôÚê.n´Û
êž,g
2
=(V
1
,V
2
∪U,V
3
,V
4
,X)´ãµ(W
n
)˜‡››XÚ¦^5‡ôÚ,χ
td
(µ(W
n
))≤5.
DOI:10.12677/pm.2021.11112131916nØêÆ
È
Ón´Ûêž,χ
td
(µ(W
n
))=5.2
,?Ø÷ãF
n
Mycielskianãµ(F
n
)››XÚê.
½n2.9 n≥3ž,χ
td
(µ(F
n
))=4.
y²ãF
n
:8P•{v}∪{v
i
|1≤i≤n},>8P•{vv
i
|1≤i≤n}∪{v
i
v
i+1
|1≤i≤n−1}.
Ø”˜„5,:vXôÚ1,:v
i
(i´Ûê)XôÚ2,:v
i
(i´óê)XôÚ3,Kf=(V
1
,V
2
,V
3
)
´÷ãF
n
˜‡››XÚ…¦^•ôÚê.qÏ•χ(F
n
)=3,χ
td
(F
n
)=3.y•Ä
÷ãMycielskianã.g=(V
1
,V
2
,V
3
∪U,X)´ãµ(F
n
)˜‡››XÚ¦^4‡ôÚ,Ï
dχ
td
(µ(F
n
))≤4.d½n2.1•χ
td
(µ(F
n
))=4=χ
td
(F
n
)+1.2
••ÄlÇãMycielskianã››XÚê.
½n2.10 n≥2ž,χ
td
(µ(F
n
))=4.
y²ãF
n
:8P•{v}∪{v
i
|1≤i≤2n},>8P•{vv
i
|1≤i≤2n}∪{v
i
v
i+1
|1≤i≤
2n…i´Ûê}.ãF
n
˜‡››XÚXe::vXôÚ1,:v
i
(i´Ûê)XôÚ2,:v
i
(i´
óê)XôÚ3,Kf=(V
1
,V
2
,V
3
)´lÇãF
n
˜‡››XÚ…¦^•ôÚê.qÏ
•χ(F
n
)=3,χ
td
(F
n
)=3.yg=(V
1
,V
2
,V
3
∪U,X)´ãµ(F
n
)˜‡››XÚ¦^4
‡ôÚ,Ïdχ
td
(µ(F
n
))≤4.d½n2.1•χ
td
(µ(F
n
))=4=χ
td
(F
n
)+1.2
Ä7‘8
I[g,‰ÆÄ7‘8(11761070,61662079);2021c#õ‘Æg£«g,Ä7éÜ‘
8(2021D01C078);2020c#õ“‰ŒÆ˜6;’!˜6‘§‘8]Ï"
ë•©z
[1]Gera,R.,Rasmussen,C.W.andHorton,S.(2006)DominatorColoringsandSafeClique
Partitions.CongressusNumerantium,181,19-32.
[2]Kazemi,A.P.(2015)TotalDominatorChromaticNumberofaGraph.TransactionsonCom-
binatorics,4,57-68.
[3]Zhou,Y.andZhao,D.(2019)OnDominationColoringinGraphs.ArXiv:1909.03715
[4]Chithra,K.P.andMayamma,J.(2021)TotalDominationColoringofGraphs.Journalof
MathematicsandComputerScience,11,442-458.
[5]Mycielski,J.(1995)Surlecoloriagedesgraphs.ColloquiumMathematicum,3,161-162.
https://doi.org/10.4064/cm-3-2-161-162
DOI:10.12677/pm.2021.11112131917nØêÆ

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