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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(9),3159-3168
PublishedOnlineSeptember2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.109330
Mycielskianãà››Úfà››êïÄ
ŽŽŽ444###999ØØØMMMJJJ
1∗
§§§>>>ùùù
1†
§§§uuu°°°
2
1
#õ“‰ŒÆêƉÆÆ§#õ¿°7à
2
#õŒÆêƆXÚ‰ÆÆ§#õ¿°7à
ÂvFϵ2021c822F¶¹^Fϵ2021c912F¶uÙFϵ2021c923F
Á‡
-G=(V,E)´˜‡ëÏã"^d
G
(u,v)L«ãG¥ü‡º:uÚuƒm•á(u,v)´•
ݧ˜‡•Ý•d
G
(u,v)(u,v)´¡Š˜‡(u,v)-ÿ/‚"ãG˜‡:f8X⊆V‰ãG
˜‡fà8§XJéX¥?¿ü‡º:a,b,3ãG¥Ñ•3˜‡(a,b)-ÿ/‚¦(a,b)-ÿ
/‚þ¤kº:ÑáuX.aq/§ãG˜‡:f8X⊆V‰ãG˜‡à8§XJéX
¥?¿ü‡º:a,b,ãG¥z˜^(a,b)-ÿ/‚þ¤kº:ÑáuX"ãG˜‡:f
8D⊆V‰ãG˜‡ ››8§XJV-D¥z˜‡º:Ñ–k˜‡:3D¥.V:
f8X¡•Gfà(½à)››8§XJXQ´fà(½à)8q´››8"ãGfà(½à)›
›ê§´:ê•fà(½à)››8¤•¹:ê§P•γ
wcon
(G)(½γ
con
(G)).©Ì‡‰Ñ
˜AÏãMycielskianã››ê!fà››êÚà››ê(ƒŠ"
'…c
››8§à››ê§fà››ê§Mycielskianã§ã§Üã
ResearchonConvexandWeakly
ConvexDominationNumbersof
MycielskianGraphs
∗1˜Šö
†ÏÕŠö
©ÙÚ^:Ž4#9ØMJ,>ù,u°.Mycielskianãà››Úfà››êïÄ[J].A^êÆ?Ð,2021,
10(9):3159-3168.DOI:10.12677/aam.2021.109330
Ž4#9ØMJ
XieKeLaiRebuhati
1∗
HongBian
1†
,HaizhengYu
2
1
SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Aug.22
nd
,2021;accepted:Sep.12
th
,2021;published:Sep.23
rd
,2021
Abstract
Thedistanced
G
(u,v)betweentwoverticesuandvinaconnectedgraphG= (V,E)is
thelengthoftheshortest(u,v)pathinG.A(u,v)-pathoflengthd
G
(u,v)iscalleda
(u,v)-geodesic.AsubsetX⊆ViscalledweaklyconvexinGifforeverytwovertices
a,b∈X,thereexistsan(a,b)-geodesic,whoseallverticesbelongtoX,andasubset
X⊆V iscalledconvexinGifforeverytwoverticesa,b∈X,forevery(a,b)-geodesic,
whoseallverticesbelongtoX.AsubsetD⊆ViscalleddominatinginG,ifforevery
vertexofV−DhasatleastoneneighborinD.AsetX⊆Viscalledweaklyconvex
(orconvex)dominatingsetinGifitisweaklyconvex(orconvex)anddominating.The
weaklyconvex(orconvex)dominationnumberofagraphGistheminimumcardinalityof
aweaklyconvex(orconvex)dominatingsetofG,denotedbyγ
wcon
(G)(orγ
con
(G)),
respectively.Inthispaper,wepresenttheexactlyvaluesofthedominationnumbers,
weaklyconvexdominationnumbersandconvexdominationnumbersforMycielskian
graphsofsomespecialgraphs.
Keywords
DominatingSet,ConvexDominationNumber,WeaklyConvexDominationNumber,
MycielskianGraph,CompleteGraph,CompleteBipartiteGraph
Copyright
c
2021byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
DOI:10.12677/aam.2021.1093303160A^êÆ?Ð
Ž4#9ØMJ
1.0
©¥¤•ÄÑ´{ü,ÕëÏã.-G=(V(G),E(G))´˜‡{üã.év∈V(G),
^N
G
(v)={u∈V(G)|uv∈E(G)}L«:vm+•,N
G
[v]=N
G
(v)∪{u}L«:v
4+•.-d
G
(v)=|N
G
(v)|L«ãG¥:vÝ,w,d
G
(v)=|N
G
(v)|.éuº:f8S⊆V,
^N
G
(S)=
S
v∈S
N(v)L«8ÜSm+•,N
G
[S]=N(S)
S
SL«8ÜS4+•.3ëÏ
ãG¥u,vü:ƒmåld
G
(u,v)´•uÚvƒm•á´•Ý,•¡•(u,v)-ÿ/‚.éu8
ÜA⊆V(G),XJN
G
(A)=V,¡8ÜA⊆V(G)•ãG››8.XJN
G
[A]=V,…pf
ãG[A]´ëÏ,@o¡8ÜA´ãGëÏ››8.(ëÏ)››êγ(G)(γ
c
(G))´ãGê•
(ëÏ)››8¤•¹:ê.ãG¹k•ê(ëÏ)››8‰γ(G)-8Ü(γ
c
(G)-8
Ü).XJéu8ÜX¥?¿ü‡:a,b•3˜^(a,b)-ÿ/‚,¦ÿ/‚þ¤k:Ñá
u8ÜX,ù8ÜX‰fà8.XJ8ÜXQ´fà8q´››8,¡X´fà››8.
γ
wcon
(G)L«ãGfà››ê´ãG¥ê•fà››8¤•¹:ê.XJéu8ÜX
¥?¿ü‡:a,b,¤k(a,b)-ÿ/‚þ:Ñáu8ÜX,ù8ÜX‰à8.XJ8ÜX
Q´à8q´››8,¡X´à››8.γ
con
(G)L«ãGà››ê´ãG¥ê•à››
8¤•¹:ê.
à››êÚfà››ê•@´dTopp[1]JÑ,ÏLy››8¥?¿ü‡!:ƒm
ë•á,lU?ëÏ››3Ï&äO¥A^.32004c,Lema´nska[2]ïÄf
à››Úà››†Ù§››aëêƒm'X;AO/,‰Ñà››êÚëÏ››êƒn
Kã•x.Ó32004c,Raczek[3]y²(½˜‡ãfà››8Úà››8´˜‡NP-
¯K.32010c,RaczekÚLema´nska[4]ïÄ‚¡fà››êÚà››ê,¿‰Ñ˜
AÏ‚¡à››êÚfà››ê(ƒŠ.Ó˜cLema´nska[5]‰Ñ˜‡ãfà››ê
Nordhaus-Gaddum(J.ãGfà››¿©ê´•¦fà››êO\¤I‡¿©•>
ê,Dettlaffa3©z[6]¥,ÄgïÄãGfà››¿©ê,Äk‰Ñ¿©ãG˜^>ƒ
fà››ê†ãGfà››êƒmŒ±?¿Œ;Ùg,‰ÑãGfà››y©ê
A‡þ..32019c,Rosicka[7]Šâ˜‡ãG=(V,E)ÚãGº:8V˜‡˜†π,½Â˜
acÎãπG,ÄkéùacÎãà››8Úfà››85ŸŠ';Ùg,‰ÑüaAÏc
Îã•x;•,y²ãG†éAcÎãfà››êŒ±´?¿Œ;cÎãà›
›êÃ{^ ãGà››ê5.½.Ó32019c,Lema´nska[8]<ÄkïÄfà››êÚë
Ï››êƒm'X,¿‰Ñ÷vγ
wcon
(G)=γ
c
(G)ãG•x;„y²3˜„œ/e,ã
ëÏ››ê†fà››êŒ±?¿Œ;d,„ïÄ>éfà››êK•.
•Ïé˜aäk?¿ŒÚêعn/ãa,Mycielski[9]u1955cJÑ˜«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,Ù¥x
i
´v
i
€:(1≤i≤n),u¡•µ(G) Š:.Mycielskian ãº:8
´V(µ(G)) = V(G)∪V
0
(G)∪u,>8•E(µ(G)) = E(G)
S
{v
1
x
j
: v
i
v
j
∈E(G),1 ≤i≤n}
S
{x
i
u:
x
i
∈V
0
(G),1 ≤i≤n}.©‰Ñ˜AÏãMycielskianã››ê,à››êÚfà››ê
(ƒŠ.
DOI:10.12677/aam.2021.1093303161A^êÆ?Ð
Ž4#9ØMJ
2.̇(J
Ï•ãGz˜‡à››8˜½´˜‡fà››8,z˜‡fà››8˜½´˜‡ëÏ››
8,z˜‡ëÏ››8w,´˜‡››8,ÏdãG››ê!ëÏ ››ê!fà››êÚà›
›êkXe˜‡Øª'Xó.
5Ÿ1[2]:éu?¿ëÏãG÷vγ(G) ≤γ
c
(G) ≤γ
wcon
(G) ≤γ
con
(G).
Figure1.Mycielskiangraphofcomplete
graphK
n
ã1.ãK
n
Mycielskianã
3ù!¥,̇ïĘAÏãMycielskianã››ê,fà››êÚà››ê.
½n1:-K
n
•n‡:ã.Kγ(µ(K
n
)) = 2,γ
wcon
(µ(K
n
)) = γ
con
(µ(K
n
))=3.
y²bK
n
º:8•V(K
n
)={v
1
,v
2
,...,v
n
},Ù€:8•V
0
(K
n
)={x
1
,x
2
,...,x
n
}.´
•ãK
n
¥?¿˜‡:U››K
n
¥Ù§¤k:,Š:uŒ±››µ(K
n
)¥¤k€
:.éu?¿i=1,2,...,n,{u,v
i
}w,´µ(K
n
)˜‡››8(„ã1),γ(µ(K
n
))≤2.
qµ(K
n
)¥?¿˜‡ü:8w,ØU››Ø§±Ù§¤k:.Ïdγ(µ(K
n
))≥2.nþ¤
ã,γ(µ(K
n
)) = 2.
dµ(K
n
)(Œ•,éu?¿i6=j,i,j=1,2,...,n,kd
µ(K
n
)
(u,x
j
)=1,d
µ(K
n
)
(v
i
,x
j
)=
1,d
µ(K
n
)
(u,v
i
)=2,…ux
j
v
i
´uÚv
i
ƒm˜^ •á´.K{u,x
j
,v
i
}w,´µ(K
n
)˜‡fà
››8,γ
wcon
(µ(K
n
))≤3.d5Ÿ1Úγ(µ(K
n
))=2Œ•,γ
wcon
(µ(K
n
))≥2.y•Iy²µ(K
n
)
?¿˜‡f8ÑØ´µ(K
n
)fà››8=Œ.Šâµ(K
n
)¥: ˜,©•±en«œ/:
œ/1f8ü‡:Ñ uV(K
n
).Ø”˜„5,b{v
i
,v
j
},i6=j,i,j=1,2,...,n´
uV(K
n
)˜‡f8,K{v
i
,v
j
}´µ(K
n
)˜‡fà8,Ø´µ(K
n
)˜‡››8,Ï•
:uØ{v
i
,v
j
}¤››.
œ/2f8ü‡:Ñ uV
0
(K
n
).b{x
i
,x
j
},i6=j,i,j=1,2,...,n´ uV
0
(K
n
)
˜‡f8,K{x
i
,x
j
}QØ´µ(K
n
)˜‡››8,•Ø´µ(K
n
)˜‡fà8,Ï
DOI:10.12677/aam.2021.1093303162A^êÆ?Ð
Ž4#9ØMJ
•d
µ(K
n
)
(x
i
,x
j
)=2,x
i
Úx
j
¤k•á´Sܺ:ÑØ3{x
i
,x
j
}¥,d,x
k
,k6=i,j,k=
1,2,...,nØ{x
i
,x
j
}¤››.
œ/3f8¥˜‡º:3V(K
n
), ,˜‡º:3V
0
(K
n
). b{v
i
,x
j
},i6=j,i,j=
1,2,...,n´ù˜‡f8,ei6= j,K{v
i
,x
j
}´µ(K
n
)˜‡fà8,Ø´µ(K
n
)˜‡›
›8,Ï•x
i
vk››.ei= j,K{v
i
,x
j
}´µ(K
n
)˜‡››8,Ø´µ(K
n
)˜‡fà8,
Ï•džd
µ(K
n
)
(v
i
,x
i
) = 2,§‚ƒm•á´Sܺ:Ø3{v
i
,x
i
}¥,†fà8½Âgñ.
œ/4f8¥˜‡º:´{u},,˜‡º:3V(K
n
) ½V
0
(K
n
) ¥.b{u,x
i
},i=
1,2,...,n½{u,v
i
},i=1,2,...,n´ù˜‡f8,K{u,x
i
}´µ(K
n
)˜‡fà8,Ø
´µ(K
n
)˜‡››8,Ï•v
i
vk››.{u,v
i
}´µ(K
n
)˜‡››8,Ø´µ(K
n
)˜
‡fà8,Ï•džd
µ(K
n
)
(u,v
i
)=2,§‚ƒm•á´Sܺ:Ø3{u,v
i
}¥,†fà8
½Âgñ.nþŒ•,γ
wcon
(µ(K
n
)) ≥3.(ؤá.
d››8½ÂŒ•,{v
i
,v
j
,x
k
},i6=j6=k,i,j,k=1,2,...,nÄk´µ(K
n
) ˜‡››
8,qduù‡8Ü¥?¿ü‡:ƒm•á´k…=k˜^…•á´•Ý•1,dà
8½Â,{v
i
,v
j
,x
k
}q´µ(K
n
) ˜‡à8,Ïdγ
con
(µ(K
n
))≤3.d5Ÿ1Ú±þ?ØŒ
•γ
con
(µ(K
n
)) ≥γ
wcon
(µ(K
n
)) = 3,•γ
con
(µ(K
n
)) ≥3.¤±γ
con
(µ(K
n
)) = 3.
½n2:-K
m,n
´Üã.Kγ(µ(K
m,n
)) = γ
wcon
(µ(K
m,n
)) = γ
con
(µ(K
m,n
)) = 3.
y²bXÚY´Üãü‡:f8.-X={v
1
,v
2
,...,v
m
},Y={w
1
,w
2
,...,w
n
}.
X8Ü€:•X
0
={x
1
,x
2
,...,x
m
},Y8Ü€:•Y
0
={y
1
,y
2
,...,y
n
}(„ã2).é?
¿i=1,2,...,m,j=1,2,...,n,{u,x
i
,y
j
}w,´µ(K
m,n
)˜‡››8,γ(µ(K
m,n
))≤3.
qµ(K
m,n
)¥?¿˜‡ü:8w,ØU››Ø§±Ù§¤k:.Ïdγ(µ(K
m,n
))≥2.y•
Iy²µ(K
m,n
)?¿˜‡f8ÑØ´µ(K
m,n
)››8=Œ.Šâµ(K
m,n
)¥: ˜,©
•±eo«œ/:
œ/1f8ü‡:Ñ uX(½Y).Ø”˜„5,b{v
i
,v
j
},i6=j,i,j=1,2,...,m
´ uX˜‡f8,KX8€:Úu:ØU››;Ón,e{w
i
,w
j
},i6=j,i,j=
1,2,...,n´ uY˜‡f8,KY8€:Úu:ØU››;{v
i
,w
j
},i= 1,2,...,m,j=
1,2,...,n´ uX∪Y˜‡f8,Ku:ØU››.
œ/2f8ü‡:Ñ uX
0
½Y
0
.b{x
i
,x
j
},i6=j,i,j=1,2,...,m´ uX
0

˜‡f8,KX,Y€:ÚX
0
¥Øx
i
,x
j
ƒ:ÑØU››;{y
i
,y
j
},i6=j,i,j=
1,2,...,n´ uY
0
˜‡f8,KX,Y€:ÚY
0
¥Øy
i
,y
j
ƒ:ÑØU››.
{x
i
,y
j
},i= 1,2,...,m,j= 1,2,...,n´ uX
0
∪Y
0
˜‡f8,KX
0
¥Øx
i
ƒ:ÚY
0
¥Øy
j
ƒ:ÑØU››.
œ/3f8¥˜‡º:3X∪Y,,˜‡º:3X
0
∪Y
0
.b{v
i
,x
j
},i,j= 1,2,...,m´
ù˜‡f8,KX¥Øv
i
ƒ:ÚX
0
¥Øx
j
ƒ:ÑØU››;e{w
i
,y
j
},i,j
=1,2,...,n´ù˜‡f8,KY¥Øw
i
ƒ:ÚY
0
¥Øy
j
ƒ:ÑØU›
›;e{v
i
,y
j
},i=1,2,...,m,j=1,2,...,n´ù˜‡f8,KX
0
ØU››;e{w
i
,x
j
},i=
1,2,...,n,j= 1,2,...,m´ù˜‡f8,KY
0
ØU››.
DOI:10.12677/aam.2021.1093303163A^êÆ?Ð
Ž4#9ØMJ
Figure2.Mycielskiangraphofcompletebipartite
graphK
m,n
ã2.ÜãK
m,n
Mycielskianã
œ/4f8¥˜‡º:´{u},,˜‡º:3X∪Y½X
0
∪Y
0
¥.b{u,v
i
},i=
1,2,...,m´ù˜‡f8,KX¥Øv
i
ƒ:ÑØU››;e{u,w
j
},j=1,2,...,n´
ù˜‡f8,KY¥Øw
j
ƒ:ÑØU››;e{u,x
i
},i=1,2,...,m´ù˜‡
f8,KX¥:ÑØU ››;e{u,y
j
},j=1,2,...,n´ù˜‡f8,KY¥:ÑØ
U››.nþŒ•,γ(µ(K
m,n
)) ≥3.(ؤá.
d››8½ÂŒ•,{u,x
i
,y
j
},i=1,2,...,m,j =1,2,...,nÄk´µ(K
m,n
)˜‡›
›8,qduù‡8Ü¥u:†Ù§ü‡:ƒm•á´k…=k˜^…•á´•Ý
•1,d
µ(K
m,n
)
(x
i
,y
j
)=2,x
i
Úy
j
˜^•á´þ:u•3ù‡8Ü¥,dfà8½
Â,{u,x
i
,y
j
}q´µ(K
m,n
)˜‡fà8,Ïdγ
wcon
(µ(K
m,n
))≤3.d5Ÿ1Ú±þ?ØŒ
•γ
wcon
(µ(K
m,n
)) ≥γ(µ(K
m,n
)) = 3,•γ
wcon
(µ(K
m,n
)) ≥3.¤±γ
wcon
(µ(K
m,n
)) = 3.
du{u,x
i
,y
j
},i= 1,2,...,m,j= 1,2,...,nù‡8 Ü¥u:†Ù§ü‡:ƒm•á´k…=
k˜^…•á´•Ý•1,d
µ(K
m,n
)
(x
i
,y
j
)=2,x
i
Úy
j
¤k•á´þ:u•3ù‡8Ü
¥,dà8½Â,{u,x
i
,y
j
}q´µ(K
m,n
)˜‡à8,Ïdγ
con
(µ(K
m,n
))≤3.d5Ÿ1Ú±þ
?ØŒ•γ
con
(µ(K
m,n
)) ≥γ
wcon
(µ(K
m,n
)) = 3,•γ
con
(µ(K
m,n
)) ≥3.¤±γ
con
(µ(K
m,n
)) = 3.
½n3:-K
1,n−1
´(ã,K,γ(µ(K
1,n−1
)) = 2,γ
wcon
(µ(K
1,n−1
)) = γ
con
(µ(K
1,n−1
)) = 3.
y²bK
1,n−1
º:8•V(K
1,n−1
)={v
1
,v
2
,...,v
n
},Ù¥v
1
´K
1,n−1
¥%:,Ù€
:8•V
0
(K
1,n−1
) = {x
1
,x
2
,...,x
n
}.v
1
Œ±››(ã¥Ù§¤k:Ú€:8¥{x
2
,x
3
,...,x
n
}
(„ã3).{v
1
,x
1
}w,´µ(K
1,n−1
)››8.γ(µ(K
1,n−1
)) ≤2.qµ(K
1,n−1
)¥?¿˜‡ü
:8w,ØU››Ø§±Ù§¤k:.Ïdγ(µ(K
1,n−1
)) ≥2.nþ¤ã,γ(µ(K
1,n−1
)) = 2.
dµ(K
1,n−1
)(Œ•,éu?¿j= 1,2,...,n, kd
µ(K
1,n−1
)
(v
1
,x
j
) = 1(j6= 1),d
µ(K
1,n−1
)
(u,x
j
)
=1,d
µ(K
1,n−1
)
(v
1
,u)=2,…ux
j
v
1
(j6=1)´uÚv
1
ƒm˜^•á´.K{u,x
j
,v
1
}j6=1,j=
DOI:10.12677/aam.2021.1093303164A^êÆ?Ð
Ž4#9ØMJ
Figure3.Mycielskiangraphofstargraph
K
1,n−1
ã3.(ãK
1,n−1
Mycielskianã
2,...,n,w,´µ(K
1,n−1
)˜‡fà››8,γ
wcon
(µ(K
1,n−1
)) ≤3.d5Ÿ1Úγ(µ(K
1,n−1
)) =
2Œ•γ
wcon
(µ(K
1,n−1
))≥2.y•Iy²µ(K
1,n−1
)?¿˜‡f8ÑØ´µ(K
1,n−1
)fà
››8=Œ.Šâµ(K
1,n−1
)¥: ˜,©•±eo«œ/:
œ/1f8ü‡:Ñ uV(K
1,n−1
).Ø”˜„5,b{v
i
,v
j
},i6=j,i,j=1,2,...,n´
uV(K
1,n−1
)˜‡f8,K{v
i
,v
j
}Ø´µ(K
1,n−1
)˜‡››8,Ï•:uØ{v
i
,v
j
}¤
››.K{v
i
,v
j
}Ø´µ(K
1,n−1
)fà››8.
œ/2f8ü‡:Ñ uV
0
(K
1,n−1
).b{x
i
,x
j
},i6= j,i,j= 1,2,...,n´ uV
0
(K
1,n−1
)
˜‡f8,K{x
i
,x
j
}Ø´µ(K
1,n−1
)››8,Ï•V
0
(K
1,n−1
)¥Øx
i
Úx
j
ƒ:Ñ
vk››,•Ø´µ(K
1,n−1
)˜‡fà8,Ï•d
µ(K
1,n−1
)
(x
i
,x
j
)= 2,x
i
Úx
j
¤k•á´
Sܺ:ÑØ3{x
i
,x
j
}¥.K{x
i
,x
j
}Ø´µ(K
1,n−1
)fà8››8.
œ/3f8¥˜‡º:3V(K
1,n−1
),,˜‡º:3V
0
(K
1,n−1
).bù‡f8
´{v
1
,x
1
},dud
µ(K
1,n−1
)
(v
1
,x
1
) = 2§‚ƒm •á´Sܺ:Ø3{v
1
,x
1
}¥,K{v
1
,x
1
}
Ø´µ(K
1,n−1
)fà ››8;eù‡f8´{v
1
,x
j
},j=,2,...,n,Kx
1
ØU› ›;eé?¿
i,j6=1,i,j=2,3,...,n,ù‡f8´{v
i
,x
j
},Kù‡8Ü¥:ØU››µ(K
1,n−1
)¥
¤k:.nþ¤ã,˜‡ º:3V(K
1,n−1
),,˜‡º:3V
0
(K
1,n−1
)¥f8Ø´µ(K
1,n−1
)
fà››8.
œ/4f8¥˜‡º:´{u},,˜‡º:3V(K
1,n−1
)½V
0
(K
1,n−1
)¥.bù‡
f8´{u,x
j
},j=1,2,...,nK{u,x
j
}´µ(K
1,n−1
)˜‡fà8,Ø´µ(K
1,n−1
)˜‡›
›8,Ï•ù‡8ÜØU››µ(K
1,n−1
)¥¤k:;ef8´{u,v
1
}, K:uÚ:v
1
ƒm
•á´þ:Ø3ù‡8ÜS;ef8´{u,v
j
},j6=1,j=2,3,...,n,KV(K
1,n−1
)¥
:v
2
,v
3
,...,v
n
,ØU››.nþ¤ã,˜‡ º:´{u},,˜‡º:3V(K
1,n−1
)½V
0
(K
1,n−1
)¥
f8Ø´µ(K
1,n−1
)fà››8.nþŒ•,γ
wcon
(µ(K
1,n−1
)) ≥3.(ؤá.
DOI:10.12677/aam.2021.1093303165A^êÆ?Ð
Ž4#9ØMJ
d››8½ÂŒ•,{u,x
1
,x
j
},j6=1,j=2,3,...,nÄk´µ(K
1,n−1
)˜‡››8,qdu
:u†Ù§ü‡:ƒm•á´k…=k˜^…•á´•Ý•1,d
µ(K
1,n−1
)
(x
1
,x
j
)=2…ùü
‡:ƒm•á´þ:•3{u,x
1
,x
j
}¥,dà8½Â,{u,x
1
,x
j
}q´µ(K
1,n−1
)˜‡à8,
Ïdγ
con
(µ(K
1,n−1
))≤3.d5Ÿ1Ú±þ?ØŒ•γ
con
(µ(K
1,n−1
))≥γ
wcon
(µ(K
1,n−1
))=3,
•γ
con
(µ(K
1,n−1
)) ≥3.¤±γ
con
(µ(K
1,n−1
)) = 3.
½n4:-W
n
´‡Óã,Kγ(µ(W
n
)) = 2,γ
wcon
(µ(W
n
)) = γ
con
(µ(W
n
)) = 3.
y²bW
n
º:8V(W
n
)={v
1
,v
2
,...,v
n
},Ù¥v
1
´¥%:, Ù€:8V
0
(W
n
)=
{x
1
,x
2
,...,x
n
}.v
1
Œ±››V(W
n
)¥¤k:ÚV
0
(µ(W
n
))¥€:{x
2
,x
3
,...,x
n
}(„ã4).
w,{v
1
,x
1
}´µ(W
n
)˜‡››8.γ(µ(W
n
)) ≤2.qµ(W
n
)¥?¿˜‡ü:8w,ØU›
›Ø§±Ù¦¤k:.Ïdγ(µ(W
n
)) ≥2.nþ¤ã,γ(µ(W
n
)) = 2.
Figure4.MycielskiangraphofwheelgraphW
n
ã4.ÓãW
n
Mycielskianã
dµ(W
n
) (Œ•,éu?¿j=2,...,n,kd
µ(W
n
)
(v
1
,x
j
)=1,d
µ(W
n
)
(u,x
j
)=1,
d
µ(W
n
)
(v
1
,u)=2,…ux
j
v
1
´uÚv
1
ƒm˜^•á´.K{u,x
j
,v
1
}w,´µ(W
n
) ˜‡f
à››8,γ
wcon
(µ(W
n
))≤3. d5Ÿ1Úγ(µ(W
n
))=2 Œ•,γ
wcon
(µ(W
n
))≥2.y•Iy
²µ(W
n
)?¿˜‡f8ÑØ´µ(W
n
)fà››8=Œ.Š âµ(W
n
)¥: ˜,©•±
eo«œ/:
œ/1f8ü‡:Ñ uV(W
n
).Ø”˜„5,b{v
i
,v
j
},i6=j,i,j=1,2,...,n´
uV(W
n
)˜‡f8,K{v
i
,v
j
}Ø´µ(W
n
)˜‡››8,Ï•ÃØ=ü‡:uÑØU
{v
i
,v
j
}¤››.K{v
i
,v
j
}Ø´µ(W
n
)fà››8.
œ/2f8ü‡:Ñ uV
0
(W
n
).b{x
i
,x
j
},i6=j,i,j=1,2,...,n´ uV
0
(W
n
)
˜‡ f8,K{x
i
,x
j
}Ø´µ(W
n
)››8,Ï•V
0
(W
n
)¥Øx
i
Úx
j
ƒ:Ñv k›
DOI:10.12677/aam.2021.1093303166A^êÆ?Ð
Ž4#9ØMJ
›,•Ø´µ(W
n
)˜‡fà8,Ï•d
µ(W
n
)
(x
i
,x
j
)=2,x
i
Úx
j
¤k•á´Sܺ:ÑØ
3{x
i
,x
j
}¥.K{x
i
,x
j
}Ø´µ(W
n
)fà8››8.
œ/3f8¥˜‡º:3V(W
n
),,˜‡º:3V
0
(W
n
).bù‡f8´{v
1
,x
1
},
dud
µ(W
n
)
(v
1
,x
1
)=2§‚ƒm•á´Sܺ:Ø3{v
1
,x
1
}¥,K{v
1
,x
1
}Ø´µ(W
n
)
fà››8;eù‡f8´{v
1
,x
j
},j =,2,...,n,Kx
1
ØU››;eù‡f8
´{v
i
,x
j
},i,j6=1,Kù‡8Ü¥:ØU››µ(W
n
)¥¤k:.nþ¤ã,˜‡º:3V(W
n
),
,˜‡º:3V
0
(W
n
)¥f8Ø´µ(W
n
)fà››8.
œ/4f8¥˜‡º:´{u},,˜‡º:3V(W
n
)½V
0
(W
n
)¥.bù‡f8
´{u,x
j
},j=1,2,...,nK{u,x
j
}´µ(W
n
)˜‡fà8,Ø´µ(W
n
)˜‡››8,Ï•ù
‡8ÜØU››µ(W
n
)¥¤k:;ef8´{u,v
1
},K:uÚ:v
1
ƒm•á´þ:Ø
3ù‡8ÜS;ef8´{u,v
j
},j6=1,K:uÚ:v
j
ƒm•á´þ:Ø3ù‡8ÜS
…{u,v
j
}ØU››µ(W
n
)¥¤k:.nþ¤ã,˜‡º:´{u},,˜‡º:3V(W
n
)½V
0
(W
n
)
¥f8Ø´µ(W
n
)fà››8.nþŒ•,γ
wcon
(µ(W
n
)) ≥3.(ؤá.
d››8½ÂŒ•,é?¿j6=1,j=1,2,...,n,{u,x
1
,x
j
}Äk´µ(W
n
)˜‡››
8,qdu:u†Ù¦ü‡:ƒm•á´k…=k˜^…•á´•Ý•1,d
µ(W
n
)
(x
1
,x
j
)=2
…ùü‡:ƒm•á´þ:•3{u,x
1
,x
j
}¥,dà8½Â,{u,x
1
,x
j
}q´µ(W
n
)˜
‡à8,Ïdγ
con
(µ(W
n
))≤3. d5Ÿ1Ú±þ?ØŒ•γ
con
(µ(W
n
))≥γ
wcon
(µ(W
n
))=3,
•γ
con
(µ(W
n
)) ≥3.¤±γ
con
(µ(W
n
)) = 3.
Ä7‘8
I[g,‰ÆÄ7‘8(11761070,61662079)¶2021c#õ‘Æg£«g,Ä7éÜ‘
8(2021D01C078)¶2020c#õ“‰ŒÆ˜6;’!˜6‘§‘8]Ï"
ë•©z
[1]Topp,J.(2002)PersonalCommunication.Gda´nskUniversityofTechnology,Gda´nsk.
[2]Lema´nska,M. (2004) Weakly ConvexandConvexDominationNumbers. OpusculaMathemat-
ica,24,181-188.
[3]Raczek,J.(2004)NP-CompletenessofWeaklyConvexandConvexDominatingSetDecision
Problems.OpusculaMathematica,24,189-196.
[4]Raczek,J.andLema´nska,M.(2010)ANoteontheWeaklyConvexandConvexDomination
NumbersofaTorus.DiscreteAppliedMathematics,158,1708-1713.
https://doi.org/10.1016/j.dam.2010.06.001
[5]Lema´nska,M.(2010)Nordhaus-GaddumResultsforWeaklyConvexDominationNumberof
aGraph.DiscussionesMathematicaeGraphTheory,30,257-263.
https://doi.org/10.7151/dmgt.1491
DOI:10.12677/aam.2021.1093303167A^êÆ?Ð
Ž4#9ØMJ
[6]Dettlaff,M.,Kosari,S.,Lema´nska,M.andSheikholeslami, S.M.(2016) WeaklyConvexDom-
inationSubdivisionNumberofaGraph.Filomat,30,2101-2110.
https://doi.org/10.2298/FIL1608101D
[7]Rosicka,M.(2019)ConvexandWeaklyConvexDominationinPrismGraphs.Discussiones
MathematicaeGraphTheory,39,741-755.https://doi.org/10.7151/dmgt.2207
[8]Dettlaff,M.,Lema´nska,M.andOsula,D.(2019)OntheConnectedandWeaklyConvex
DominationNumbers.arXiv:1902.07505v1
[9]Mycielski,J.(1995)Surlecoloriagedesgraphs.ColloquiumMathematicum,3,161-162.
https://doi.org/10.4064/cm-3-2-161-162
DOI:10.12677/aam.2021.1093303168A^êÆ?Ð

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