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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
PureMathematicsnØêÆ,2023,13(4),942-947
PublishedOnlineApril2023inHans.https://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2023.134099
õÜã:õ-8Œ«OIE-/Ú
]]]
Ü“‰ŒÆ§êƆÚOÆ§[‹=²
ÂvFϵ2023c318F¶¹^Fϵ2023c419F¶uÙFϵ2023c426F
Á‡
|^‡y{§E/Ú{§Ú8ܯk©{§?ØtÜãº:õ-8Œ«OIE-
/Ú"‰Ñ•`/Ú˜‡•Y§¿(½ƒA/ÚÚê")ûõÜã:õ
-8Œ«OIE-/Ú¯K"
'…c
tÜã§IE-/Ú§õ-8§Ú8ܧŒ«O
VertexDistinguishingIE-TotalColoring
ofCompleteMultipartiteGraphsby
Multisets
YongjunWang
CollegeofMathematicsandStatistics,NorthwestNormalUniversity,LanzhouGansu
Received:Mar.18
th
,2023;accepted:Apr.19
th
,2023;published:Apr.26
th
,2023
Abstract
Inthispaper,byusingthemethodofcontradiction,themethodofconstructingcon-
©ÙÚ^:].õÜã:õ-8Œ«OIE-/Ú[J].nØêÆ,2023,13(4):942-947.
DOI:10.12677/pm.2023.134099
]
cretecoloringandthemethodofdistributingthecolorsetsinadvance,wediscuss
theIE-totalcoloringsofcompletet-partitegraphwhicharevertex-disti nguishedby
multisets.Themethodsofthecorrespondingoptimalcoloringaregivenandthechro-
maticnumbersofthecorrespondingcoloringsareobtained.Thequestionofvertex
distinguishingIE-totalcoloringofcompletemultipartitegraphsbymultisetshasbe
completelysettled.
Keywords
Completet-PartiteGraph,IE-TotalColoring,Multiset,ColorSet,Distinguishing
Copyright
c
2023byauthor(s)andHansPublishersInc.
ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.Úó
:Œ«O˜„>/Ú´dHararyF<u1985c3©z[1]¥JÑ.©z[2]¥Ú\:Œ«
O˜„/Ú,¿…ïÄ´,,((=K
1,n
),V(,n(,Ó,÷,ã˜„:Œ«O/Ú,(½
§‚˜„:Œ«OÚê.:Œ«O(šõ-8)IE-/Ú3©z[3–6]¥þkïÄ,… é
nÜãÐmïÄ.3©z[7]¥ÄgJÑ:õ-8Œ«OIE-/Ú,…éÜãÐm
ïÄ.3©¥·‚ïÄõÜã:õ-8Œ«OIE-/Ú,(½tÜã:õ-
8Œ«OIE-Úê.©3/Ú•Yþ†c<ƒ',kƒAUCÚõ.¤±ù‘óŠò‰:
õ-8Œ« O˜„/ÚYïÄJø/Ú•{Ú/Úg´,?˜Ú´Lk'˜„/Ún
ؤJ.
2.OóŠ
ãGIE-/Ú´•¦ƒº:/±ØÓÚ˜‡˜„/Ú.Ï~œ¹e,·‚?1/Ú
ž,¤^k«ôÚ^1,2,,,k5L«,… êi“LôÚƒmkŒ'X.ãG¦^k«ôÚIE-
/Ú‰ãGk-IE-/Ú.
f•ãGIE-/Ú.éu?¿x∈V(G),^
˜
C
f
(x)½ö
˜
C(x)L«:xÚ±9†xƒ'é
>Ú¤õ-8.¡
˜
C
f
(x)•xõ-Ú8ܽöÚ8Ü.w,k|
˜
C
f
(x)|=d
G
(x)+1,Ù
¥d
G
(x)L«ãG¥:xÝ.eé?¿u,v∈V,u6=v,ok
˜
C
f
(u)6=
˜
C
f
(v)K¡f´:õ-8Œ
DOI:10.12677/pm.2023.134099943nØêÆ
]
«O.
-χ
ie
v t
(G)=min{k|G•3:õ-8Œ«Ok-IE-/Ú},òχ
ie
v t
(G)¡•:õ-8Œ«
OIE-Úê.
©¥,^K
n
1
,n
2
,···,n
t
L«t‡Üº:ê©O•n
1
,n
2
,···,n
t
tÜã,1i‡Ü•
X
i
={x
(i)
1
,x
(i)
2
,···x
(i)
n
i
},|X
i
|=n
i
,n
i
<n
j
,1≤i<j≤t.
3K
n
1
,n
2
,···,n
t
˜‡k-IE-/Úe,X
t
´¹º:•õÜ,X
t
¥:Ú8Ü•
{a
j,1
,a
j,2
,···,a
j,n
1
+n
2
+...+n
t−1
+1
},Ú8Ü¥•¹n
1
+n
2
+...+n
t−1
+1«ƒ.(-EU-EÑ
ygêOŽ)
Ún2.1[8]ln‡pÉƒ¥Œ-EÑr‡|Ü‡ê•

n+r−1
r

.
ln‡p؃Óƒ¥Ñr‡Š¤-E|Ü•‰r-|Ü.r-|Ü•´cãn‡p؃Óƒ
¤8Ü¹kr‡ƒõ-f8Ü,¤±r-|Ü•‰r-õ-f8½r-f8.
·‚½,3©¥Ö˜‡r-f8ž,p¡ƒUìØ~^Sü.
3.tÜã:õ-8Œ«OIE-/Ú
½n3.1(i)n
t−1
≤n
t
≤

n
1
+n
2
+···+n
t−1
+t
t−1

−

n
1
+n
2
+···+n
t−1
+t−1
t−2

ž,
˜
χ
ie
v t
(K
n
1
,n
2
,···,n
t
)=t.
(ii)

n
1
+n
2
+···+n
t−1
+k−1
k−2

−

n
1
+n
2
+···+n
t−1
+t−1
t−2

+1≤n
t
≤

n
1
+n
2
+···+n
t−1
+k
k−1

−

n
1
+n
2
+···+n
t−1
+t−1
t−2

,k>tž,
˜
χ
ie
v t
(K
n
1
,n
2
,···,n
t
)=k.
y²kyK
n
1
,n
2
,···,n
t
Ø•3:õ-8Œ«O(k−1)−IE-/Ú,|^‡y{,btÜã•
3:õ-8Œ«O(k−1)-IE-/Ú.
duX
1
¥:¤/Ú,X
2
¥:¤/Ú,···,X
t
¥:¤/Úp؃Ó,Ø”bôÚ1/X
1
¥
:,ôÚ2/X
2
¥:,···,ôÚt−1/X
t−1
¥:.
éuk−1«pÉôÚ(n
1
+n
2
+···+n
t−1
+1)-f8,Xf8¥•¹ƒ1,2,···,t−1,@
oùf8ØU ‰•X
t
¥:Ú8Ü.•¹ôÚ1,2,···,t−1(n
1
+n
2
+···+n
t−1
+1)-f8
k

n
1
+n
2
+···+n
t−1
+t−1
t−2

‡.
qϕ

n
1
+n
2
+···+n
t−1
+k−1
k−2

−

n
1
+n
2
+···+n
t−1
+t−1
t−2

≤

n
1
+n
2
+···+n
t−1
+k−1
k−2

−

n
1
+n
2
+···+n
t−1
+t−1
t−2

+1.
tÜãعkk−1«Ú:õ-8Œ«OIE-/Ú.
e¡‰Ñ·‚étÜã:õ-8Œ«Ok-IE-/Ú/Ú•Y.
DOI:10.12677/pm.2023.134099944nØêÆ
]
Äk,‰X
i
Ü¥:/±Úi,i=1,2,···,t−1.
Ùg,[X
1
,X
2
]¥>/±ôÚ2.
[X
1
∪X
2
,X
3
]¥>/±ôÚ3
[X
1
∪X
2
∪X
3
,X
4
]¥>/±ôÚ4
.
.
.
[X
1
∪X
2
∪···X
t−2
,X
t−1
]¥>/±ôÚt−1
A
j
´˜‡n
j
•,gé‚9þ•ƒ•j,gé‚e•ƒÑ•j+1,J
j
´˜‡(n
t−1
−
n
j
)×n
j
ƒ•jÝ,j=1,2,···,t−1.5:J
t−1
´˜,en
t−2
=n
t−1
,KJ
t−2
•´˜,.
E˜‡n
t−1
×(n
1
+n
2
+···+n
t−1
+1)ÝM.¦cn
1
¤Ý•

A
1
J
1

,
1(n
1
+1)(n
1
+n
2
)¤Ý•

A
2
J
2

,1(n
1
+n
2
+1)(n
1
+n
2
+n
3
)¤Ý
•

A
3
J
3

,···1(n
1
+n
2
+···+n
t−3
+1)(n
1
+n
2
+···+n
t−2
)¤Ý•

A
t−2
J
t−2

,
1(n
1
+n
2
+···+n
t−2
+1)(n
1
+n
2
+···+n
t−1
)¤Ý•

A
t−1
J
t−1

,•˜Ý
ƒ•t.ÝMz˜1ƒl†m´Ø~,…Ù?¿ü1ØÓ.
òk«p؃ÓÚ–¹t,t+1,···,kƒ˜(n
1
+n
2
+···+n
t−1
+1)−f8(õ-8,‡
ê≥n
t
)Š•Ú8ÜéAX
t
ˆ‡º:þ,¦X
t
¥ØÓº:éAØÓf8.
x
(t)
j
éAf8•{a
j,1
,a
j,2
,···,a
j,n
1
+n
2
+···+n
t−1
+1
},,,
a
j,1
≤a
j,2
≤···≤a
j,n
1
+n
2
+···+n
t−1
+1
.ùp••B,-a
j,1
,a
j,2
,···,a
j,n
1
+n
2
+···+n
t−1
+1
fдM¥
1j1ƒ.
e¡éX
t
¥:9'é>?1Xe/Ú.
a
j,1
/>x
(1)
1
x
(t)
j
,a
j,2
/>x
(1)
2
x
(t)
j
,···,a
j,n
1
/>x
(1)
n
1
x
(t)
j
a
j,n
1
+1
/>x
(2)
1
x
(t)
j
,a
j,n
1
+2
/>x
(2)
2
x
(t)
j
,
···,a
j,n
1
+n
2
/>x
(2)
n
2
x
(t)
j
···,a
j,n
1
+n
2
+···,+n
t−2
+1
/>x
(t−1)
1
x
(t)
j
,a
j,n
1
+n
2
+···+n
t−2
+2
/>x
(t−1)
2
x
(t)
j
···
a
j,n
1
+n
2
+···+n
t−1
/>x
(t−1)
n
t−1
x
(t)
j
,a
j,n
1
+n
2
+···+n
t−1
+1
/:x
(t)
j
,j=1,2,···,n
t
.
e`²tÜã3ù«/Ú•Ye:Ú8܈؃Ó.
1.n
t−1
=n
t
ž,dÝŒ•,X
t
¥cn
t−1
‡:Ú8Ü®²‰Ñ.
(1)éuØÓÜ:Ú8Üó,X
1
,X
2
,X
t
ˆÜº:Ú8Ü¥¤¹ƒ«aØÓ.
X
1
¥:õ-Ú8ÜpˆØƒÓÚ•1,2,···,t−1.
X
2
¥:õ-Ú8ÜpˆØƒÓÚ•2,3,···,t−1.
.
.
.
X
t−1
¥:õ-Ú8ÜpˆØƒÓÚ•t−1,t.
X
t
¥:õ-Ú8ÜpˆØƒÓÚ•1,2,···,t.
ˆÜ:õ-Ú8܈؃Ó.
(2)éuÓ˜Ü:Ú8Üó,¤¹,‡ƒ‡êo´ØÓ.
˜
C(x
(l)
i
)¥ôÚl‡êðõu
˜
C(x
(l)
j
),l∈[1,t−1],i<j,i,j∈[1,n
l
].
˜
C(x
(t)
i
)¥ôÚt‡êðu
˜
C(x
(t)
j
),i<j, i,j∈[1,n
t
]
2.n
t−1
<n
t
ž.
Äk`²X
t
Üz‡:Ú8܆٦ܺ:Ú8܈؃Ó.n
t−1
<n
t
ž,´3X
t
¥®‰
DOI:10.12677/pm.2023.134099945nØêÆ
]
½cn
t−1
‡:œ¹eUY\:,džX
t
Ü:Ú8ܤ¹ƒ‡êuÙ¦Ü:Ú8ܤ¹
ƒ‡ê,X
t
Üz‡:Ú8܆٦Üº:Ú8Ü؃Ó,Ùg,Ï•,X
t
:Ú8Ü´k«p
؃ÓÚ–¹t,t+1,···,kƒ˜(n
1
+n
2
+···+n
t−1
+1)−f8¤éA,X
t
Sܺ:õ
-Ú8Üp؃Ó.e•ÄX
1
,X
2
,···,X
t−1
܃m:Ú8Ü'X.
(1)ØÓ܃mÚ8܈؃Ó.
±X
4
Ü˜:†X
7
Ü˜:•~.
3X
t
Ü®(½n
t−1
‡:œ¹e,
˜
C(x
(4)
i
)6=
˜
C(x
(7)
j
),
˜
C(x
(4)
i
)¥¤¹ôÚ4‡ê‡Œu
˜
C(x
(7)
j
)¥
¤¹ƒ4‡ê,‡¦
˜
C(x
(4)
i
)=
˜
C(x
(7)
j
),–•3X
t
¥š®(½n
t−1
‡:˜:x
p
,k
a
p,n
1
+n
2
+···+n
6
+j
=4,i∈[1,n
4
],j∈[1,n
7
].
dž,ea
p,n
1
+n
2
+n
3
+i
=4,Ké
˜
C(x
(4)
i
)†
˜
C(x
(7)
j
)'ÃK•.
•Ñy
˜
C(x
(4)
i
)=
˜
C(x
(7)
j
),Ia
p,n
1
+n
2
+n
3
+i
<4.
ba
p,n
1
+n
2
+n
3
+i
=3,@oI‡X
t
¥š®(½n
t−1
+1‡:˜:x
l
,¦a
l,n
1
+n
2
+···+n
6
+j
=
3.@oa
l,n
1
+n
2
+n
3
+i
<3.
ba
l,n
1
+n
2
+n
3
+i
=1,@oI‡X
t
¥š®(½n
t−1
+2‡:˜:x
q
,¦a
l,n
1
+n
2
+···+n
6
+j
=
1.dž,a
q ,n
1
+n
2
+n
3
+i
•U•1.
¤±
˜
C(x
(4)
i
)6=
˜
C(x
(7)
j
)ð¤á,Ù¦ØÓÜ:Ú8ÜØÓy²aq.
(2)Ә܃m:Ú8܈؃Ó.
±X
2
Üü‡:•~.3X
t
Ü®(½n
t−1
‡:œ¹e,
˜
C(x
(2)
i
)6=
˜
C(x
(2)
j
),i<j,i,j∈
[1,n
2
].
˜
C(x
(2)
i
)¥ôÚ2‡êõu
˜
C(x
(2)
j
)¥ôÚ2‡ê.
‡¦
˜
C(x
(2)
i
)=
˜
C(x
(2)
j
),–•3X
t
¥š®(½n
t−1
‡:˜:x
p
,Ù¥,a
p,n
1
+j
=2.
dž,ea
p,n
1
+i
=2,Ké
˜
C(x
(2)
i
)†
˜
C(x
(2)
j
)'ÃK•.
•Ñy
˜
C(x
(2)
i
)=
˜
C(x
(2)
j
),Ia
p,n
1
+i
=1.
dž,–•3X
t
¥š®(½n
t−1
+1‡:˜:x
q
,Ù¥,a
q ,n
1
+j
=1,dža
q ,n
1
+1
7•1.
¤±,
˜
C(x
(2)
i
)6=
˜
C(x
(2)
j
)7¤á.Ù¦SÜ:Ú8ÜØÓy²aq.
ù,·‚‰ÑtÜã:õ-8Œ«OIE-/Ú.
ë•©z
[1]Harary,F.andPlantholt,M.(1985)ThePoint-DistinguishingChromaticIndex.In:Harary,
F.andMaybee,J.S.,Eds.,GraphsandApplication,WileyInterscience,NewYork,147-162.
[2]Liu,C.J.andZhu,E.Q.(2014)GeneralVertex-DistinguishingTotalColoringsofGraphs.
JournalofAppliedMathematics,2014,ArticleID:849748.
https://doi.org/10.1155/2014/849748
[3]Chen,X.E.,Gao,Y.P.andYao,B.(2013)Vertex-DistinguishingIE-TotalColoringsofCom-
pleteBipartiteGraphsK
m,n
(m<n).DiscussionesMathematicaeGraphTheory,33,289-306.
https://doi.org/10.7151/dmgt.1659
DOI:10.12677/pm.2023.134099946nØêÆ
]
[4]•Œ,ÜW,oL+.K
2,4,p
:Œ«OIE-/Ú[J].>f†&EÆ,2020,42(12):2999-
3004.
[5]ê··,•Œ.K
4,4,p
:Œ«OIE-/Ú(4≤p≤1007)[J].¥ìŒÆÆ(g,‰Æ‡),
2020,59(4):134-143.
[6]Aa¯,•Œ.K
5,5,p
:Œ«OIE-/Ú(p≥2028)[J].uÀ“‰ŒÆÆ(g,‰Æ‡),
2022(2):16-23.
[7]•Œ,].Üã:õ-8Œ«OIE-/Ú9˜„/Ú[J].3ŒÆÆ
(nƇ),2022,60(4):838-844.
[8]Wü.|ÜêÆ[M].þ°:ÓLŒÆч,1990.
DOI:10.12677/pm.2023.134099947nØêÆ

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