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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
PureMathematicsnØêÆ,2022,12(8),1392-1398
PublishedOnlineAugust2022inHans.http://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2022.128152
ã(š5ŸïÄ
ooo´´´
1∗
§§§>>>ùùù
2†
§§§uuu°°°
2
1
#õ“‰ŒÆ§êƉÆÆ§#õ¿°7à
2
#õŒÆ§êƆ&E‰ÆÆ§#õ¿°7à
ÂvFϵ2022c724F¶¹^Fϵ2022c824F¶uÙFϵ2022c831F
Á‡
ãšnØ´ãØ¥²;¯K,§3¢S)¹¥A^•š~2•.DÚšnØ•U)
û˜ é˜<©¯K,éu(½|•õ<|©¯KDÚ˜ 阚®Ã{)û,d
dJÑ(šVg.ÜãK
1,s
¡•(ã.3ãG¥vkúº:ü‡(fãK
1,s
¡
ƒ•ƒpÕá(fã,ãG¥ƒpÕá(f㤠¤8ÜM
K
1,s
(G)‰ãG˜‡K
1,s
-
š,{¡(š.ãG¤k(š¥,¹kK
1,s
•Œ‡ê¡•ãGK
1,s
-šê,{ ¡(
šê,P•m
K
1,s
(G),¿¡dK
1,s
-š•ãG•ŒK
1,s
-š.ev´ãG,‡•ŒK
1,s
-
šM
K
1,s
(G)¥º:,K¡M
K
1,s
(G)Ú:v,eM
K
1,s
(G)ÚãG¤kº:,K
¡M
K
1,s
(G)•{(š.©|^©a?Ø•{ïÄ˜AÏãa äk(š¿‡^‡
±9(šþ!e.;,‰ÑäÚpäk{(š¿©^‡,¿…‰Ñä
±9pä{(šê(ƒŠ.
'…c
š§(š§(š꧕Œ(š§{(š
ResearchonPropertiesofStarMatchings
ofGraphs
PeirongLi
1∗
,HongBian
2†
,HaizhengYu
2
1
SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Jul.24
th
,2022;accepted:Aug.24
th
,2022;published:Aug.31
st
,2022
∗1˜Šö"
†ÏÕŠö"
©ÙÚ^:o´,>ù,u°.ã(š5ŸïÄ[J].nØêÆ,2022,12(8):1392-1398.
DOI:10.12677/pm.2022.128152
o´
Abstract
Matchingtheoryingraphisaclassicalproblemingraphtheory,andalsohasvery
widelyapplicationsinreallife.However,thetraditionalmatchingtheorycanonly
solvetheproblemofone-to-onepersonnelallocation,andthetraditionalone-to-one
matchingcannotsolvetheproblemofmulti-persongroupallocationthatdetermines
the groupleader,thus putting forward the conceptofstarmatching.Complete bipar-
titegraphK
1,s
iscalledstargraph.TwostargraphsK
1,s
withoutnocommonvertex
inthegraphGarecalledindependentstargraphs,andwecallthatthesetM
K
1,s
(G)
consistingofmutually independentstargraphsK
1,s
isaK
1,s
-matching ofthegraphG,
simplystarmatching.ThemaximumcardinalityofM
K
1,s
(G)iscalledK
1,s
-matching
numberofG,simplystarmatchingnumber.Wecallthatavertexvofsomemaxi-
mumstarmatchingM
K
1,s
(G)issaturatedbyM
K
1,s
(G).Ifthemaximumstarmatching
M
K
1,s
(G)saturated all of vertices ofG, then M
K
1,s
(G)is called perfect starmatching.In
thispaper,byusingthemethodofclassificationdiscussion,wepresentsomebounds
andnecessaryandsufficientconditionsofcontainingstarmatchingsinsomespecial
graphs;Moreover,wegivethesufficientconditionsofcontainingperfectstarmatch-
ingsinperfectbinarytreesandperfectp-arytrees,andgivetheexactlyvaluesof
perfectstarmatchingnumbersofperfectbinarytreesandperfectp-arytrees.
Keywords
Matching, StarMatching, StarMatchingNumber, MaximumStarMatching, Perfect
StarMatching
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution International License (CCBY 4.0).
http://creativecommons.org/licenses/by/4.0/
1.0
ãšnØïÄ´ãØ¥²;¯Kƒ˜,§3¢S)¹¥A^›©2•,X~„´
¯K.‘Xž“Ú¬uÐ,<‚éuãší2qkéõ#â», ©Ì‡£ã
(šÒ´Cc5ãš¥q˜#mÉ—.
(šVgªJÑžm',´šnØ¥˜‡'#LïÄ••.¯¢þ,@
31986c,Hell [1]ïÄÜãpacking¯K,=:‰½Üã˜‡8ÜB,´Ä˜‡
ãGkB-Ïfºù‡¯KAÏœ/B´˜(ã8Üž,ù‡•ŒB-packing¯K¢ŸþÒ´
(š¯K.©z[2]O˜‡õ‘ªžmŽ{5OŽ,T≥2ž?¿ãGT-(šê,¿
‰ÑT-(š˜5Ÿ.©z[3]Äu•Œ(šJÝy©‰Ñä•ŒT
+
-(šõ
‘ªžmŽ{.©z[4]|^(šê‰ÑëÏãÄuK
1,s
(šêL-AŠ±9Q-AŠ
ƒ'þ!e..©z[5]‰ÑëÏãÄuK
1,s
(šêãUþe..
©¤ïÄãÑ´k•{üã.-G= (V(G),E(G))L«˜‡ã.?¿ü‡º:þƒ{
üã¡•ã,n‡º:ãPŠK
n
.XJãGz‡º:ÝþƒÓ¡G•Kã.z‡
DOI:10.12677/pm.2022.1281521393nØêÆ
o´
º:Ý•kKã,¡•k-Kã.e˜‡ãGº:8V(G)Œ±y©•ü‡p؃š
˜f8X(G)ÚY(G),¦X(G)∪Y(G) = V(G),…éu?¿e
ij
= v
i
v
j
∈E(G)(i6= j),Ñkv
i
∈
X(G),v
j
∈Y(G),K¡ãG´Üã.e|X(G)|=m,|Y(G)|=n,…é∀v
i
∈X(G),v
j
∈Y(G),
Ñkv
i
v
j
∈E(G),K¡ãG•Üã,PŠK
m,n
.
Figure1.Classificationofbinarytree
ã1.ä©a
˜‡ëÏ{üÃã¡•äT.äT¥Ý•1:¡•“f:,^n
0
Ún
i
©OL«äT¥“f
:Úfä‡ê•i!:ê8.z‡!:–õ•kpˆfää‰pä;p=2ž¡•
ä(„ã1(a)).XJ䥓f!:•Ñy3•eÚge,…•e“f!:‚†ü,
ùä¡•ä(„ã1(b));XJ3䥤k“f!:•Ñy3•˜,
K¡Ù•{ä(„ã1(c)).päÚ{päaq½Â.w,,XJ˜‡äº:
ê•n,´•,n
2
= n
0
−1,n
1
= n−2n
0
+1.
ÜãK
1,s
¡•(ã.ãG¥Ãúº:ü‡(ãK
1,s
¡•´ƒpÕá.ãG¥
ƒpÕáK
1,s
¤¤8ÜM
K
1,s
(G)¡•ãG˜‡K
1,s
-š,{¡(š.w,,K
1,1
-š
Ò´Ï~¿Âeš;K
1,2
-šÒ´P
3
-š.ãG¤k(š¥¹kK
1,s
•Œ‡ê¡
•ãGK
1,s
-šê,PŠm
K
1,s
(G);¿¡dK
1,s
-š•ãG•ŒK
1,s
-š.ev´ãG
,‡•ŒK
1,s
-šM
K
1,s
(G)¥º:,K¡M
K
1,s
(G)Úº:v.eãG•ŒK
1,s
-šÚ
ãG¤kº:,K¡M
K
1,s
(G)•{(š.
8ck'ãšnØïÄš~´L,ãšƒ'A^Œõ •uaq´¯K˜
é˜<©,•Û•.©ïÄ(šKŒ±3ãšÄ:þ Ãõ•›.~X3<
©¯K¥,|^(šŒ±é¯ ‰Ñ(½|•õ<ê|©¯K.Äud©̇ï
ÄXe:
ÄkïÄ˜AÏãaäk(š¿‡^‡±9(šþ!e.;,‰Ñä
Úpäk{(š¿©^‡,¿…‰Ñä±9pä{(šê(ƒŠ.
2.̇(J
3!¥Äk•Ä˜AÏãa,XµÜã!Üã(šêþ!e..
½n2.1 [4]n(n≥2)äT(šêm
K
1,s
(T)7½÷v:1 ≤m
K
1,s
(T) ≤
n
1+s
(s≤∆(T)).
½n2.2-G= (X(G),Y(G))´˜‡Üã, Ù¥|X(G)|= m,|Y(G)|= n.Kn<mž, G
•¹K
1,1
-š(šêm
K
1,1
(G)÷v:1≤m
K
1,1
(G)≤n;AO/,G•ÜãK
n,m
ž,Ù(šêm
K
1,s
(K
m,n
)÷v:m
K
1,s
(K
m,n
) = min{[
m
s
],n},Ù¥1 ≤s≤m.
y²:Äk,1≤m
K
1,1
(G)w,¤á;d(ãK
1,1
½ÂŒ±•:(ãK
1,1
¥k2‡º:,1
^>,=(ãK
1,1
¤¤8ÜM
K
1,1
(G)¥ƒ´dK
1,1
¥p؃>¤¤;dÜã
DOI:10.12677/pm.2022.1281521394nØêÆ
o´
½ÂŒ•:n<mž,ÜãG= (X(G),Y(G))¥p؃>êuun^,¤±éu?¿
(š5`k:|M
K
1,1
(G)|= m
K
1,1
(G) ≤n,=Œ±1 ≤m
K
1,1
(G) ≤n.
¯¢þ,duK
m,n
•Üã,¤±X(K
m,n
)¥z˜‡º:þ†Y(K
m,n
)¥z˜‡º:ƒ
.n<mžØ”˜„5,b(ãK
1,s
¥1‡º:3X(K
m,n
)¥,s‡º:3Y(K
m,n
)¥,
K1≤s≤mž,K
1,s
-š˜½•3,qÏ•(šê´•K
m,n
¥¤Ué•õƒpÕá
(ãK
1,s
‡ê,…X(K
m,n
)¥º:p؃,¤±(šê•m
K
1,s
(K
m,n
)=min{[
m
s
],n}
w,¤á.
-T´n‡º:pä(n≥p+1),e¡½n2.3‰ÑTkK
1,s
-(š¿‡^‡.
½n2.3-T´n‡º:pä(n≥p+1).KTkK
1,s
-(š…=1≤s≤
p+1.
y²:dpä½ÂŒ±•∆(T)=p+ 1,¤±XJTkK
1,s
-(š,K1≤s≤
p+1;
qÏ•päz˜‡º:v
i
(š“f:)–õ†Ù§p+ 1‡º:ƒ,¤±1≤s≤p+1ž,T
kK
1,s
-(š.
e¡‰ÑãK
n
(šê(ƒŠ.
½n2.4 éuãK
n
,Km
K
1,s
(K
n
) = bn/(1+s)c.
y².dãK
n
½ÂŒ±•K
n
z˜‡º:v
i
Ýþ•d
K
n
(v
i
)=n−1,¤±
1 ≤s≤n−1žK
n
þkK
1,s
-š…m
K
1,s
(K
n
)Œ–•1.
e¡©•ü«œ¹y²ã•Œ(šê;Ø”k=n/(1 + s),k∈N
∗
(N
∗
“L
g,ê8K0)ž,d(ãK
1,s
½ÂŒ•:|V(K
1,s
)|=1 +s;Ø”bK
n
•Œ(šê
•m
K
1,s
(K
n
),KK
n
•Œ(š¥•¹º:‡ê•(1+s)m
K
1,s
(K
n
);
éuz˜‡n= (1+s)k, K∈N
∗
žŒ±n)•: oU3K
n
¥ék‡ØÓ…Ñ•¹1+s
‡º:fãG
i
(i= 1,2,...,k), qϕK
n
(Ù¥n= 1+s)z˜‡º:o†Ù{s‡º:ƒ,
¤±G
i
¥(šê•m
K
1
,s
(G
i
) = 1,Ïdm
K
1,s
(K
n
) = k,=dž•Œ(šê•m
K
1,s
(K
n
) = k.
k∈R
∗
\N
∗
(R
∗
“L¢ê8K0)ž,Óny².éuz˜‡n=(1+ s)kŒ±n)•:o
U3K
n
¥ébkc‡ØƒÓ…Ñ•¹1+s‡º:fãG
i
(i=1,2,...,bkc),¤±m
K
1,s
(G
i
)=
bkc,=dž•Œ(šêm
K
1,s
(K
n
)=bkc.nþ¤ã,=Œéuz˜‡n=(1+ s)k(Ù
¥k∈R
∗
),ãK
n
•Œ(šê•m
K
1,s
(K
n
) = bkc,=m
K
1,s
(K
n
) = bn/(1+s)c.
e¡‰Ñk½º:±9“f:êä(šêþ!e.,±9T(šêþ.•3
¿‡^‡.
Figure2.BinarytreeT
ã2.äT
½n2.5 -T´º:ê•n,“f:ê•n
0
ä.K1≤m
K
1,3
(T) ≤n
2
−1(n>4);²L
º:·üŒ÷v:m
K
1,3
(T) = n
2
−1…=
n
0
+n
1
+1
3
≥n
2
−1.
y²:Äky²1 ≤m
K
1,3
(T) ≤n
2
−1.¯¢þ,n>4ž,w,km
K
1,3
(T) ≥1;
y^‡y{y²m
K
1,3
(T)≤n
2
−1.bm
K
1,3
(T)>n
2
−1,d(ãK
1,3
½ÂŒ±•(
ãK
1,3
k4‡º:,…4‡º:¥∆(K
1,3
) = 3,¤±em
K
1,3
(T) >n
2
−1,KäT•ŒK
1,3
-
šê¥Ý•3º:‡êŒun
2
−1‡.qdä½ÂŒ•䕌ݕ3,…äT¥
küˆfäº:ê•n
2
,Ïd•ŒÝ•3º:‡ê•n
2
−1†bgñ,=m
K
1,3
(T) ≤n
2
−1,
DOI:10.12677/pm.2022.1281521395nØêÆ
o´
nþŒ•1 ≤m
K
1,3
(T) ≤n
2
−1(n>4).
e¡y²²Lº:·üŒ÷v:m
K
1,3
(T) = n
2
−1…=
n
0
+n
1
+1
3
≥n
2
−1.
7‡5:m
K
1,3
(T) = n
2
−1,K˜½k4(n
2
−1) ≤n,qÏ•n
0
∗0+n
1
∗1+n
2
∗2 = n−1,
¤±4(n
2
−1) ≤2n
2
+n
1
+1,=n
2
−1 ≤
n
0
+n
1
+1
3
.
¿©5:däVgŒ•Ý•3º:êT•n
2
−1,…†Ù{n‡ØÓº:ƒ.du
ä´ëÏÃã…•ŒÝ•3,¤±Œ±ò?¿ä±eã2/ª?1±›,IÏLº:
·üüØn
2
−1‡3ݺ:üüƒåü‡º:œ¹(Xã1(a)¥œ¹®ü Ø),Ïd3®
•Ý•3º:êT•n
2
−1œ¹e•Iä¥1Ý:Ú2Ý:êƒÚŒu3(n
2
−1),…
ÏLº:·üüØn
2
−1‡3ݺ:üü ƒëœ¹(Xã1(a)¥œ¹®üØ),=Œ
Ñm
K
1,3
(T) = n
2
−1.dun
2
−1 ≤
n
0
+n
1
+1
3
,=3(n
2
−1) ≤n
0
+n
1
+1,ä¥1Ý:Ú2Ý
:ê©O•n
0
Ún
1
+1,¤±Œ±Ñm
K
1,3
(T) = n
2
−1.
Figure3.BinarytreeT
0
1
ã3.äT
0
1
ã1(b)¥n
2
−1 = 4,
n
0
+n
1
+1
3
=
7
3
,=n
2
−1 ≥
n
0
+n
1
+1
3
,w,m
K
1,3
(T
2
) = 2; ã1(c)¥n
2
−1 = 6,
n
0
+n
1
+1
3
= 3,=n
2
−1 ≥
n
0
+n
1
+1
3
,w,m
K
1,3
(T
2
) = 2;ã3=•ã1(a)²Lº:·ü¤/
¤ã,w,÷vm
K
1,3
(T
0
1
)=n
2
−1 = 2.
e¡½n2.6ÚíØ2.7‰Ñ{päÚ{ê©Ok{K
1,p
-(šÚ{K
1,2
-
(š¿©^‡,¿3{päÚ{ê©Ok{K
1,p
-(šÚ{K
1,2
-(šž,
‰Ñ{K
1,p
-(šÚ{K
1,2
-(šê(ƒŠ.
Figure4.Perfectp-arytreeT
ã4.{päT
½n2.6 -T´n‡º:{pä.Kéu?¿m= log
p
[1+(p−1)n](m∈N
∗
)k:
DOI:10.12677/pm.2022.1281521396nØêÆ
o´
(i)m= log
p
[1+(p−1)n]•Ûêž,äT¥vk{K
1,p
-š;
(ii)m= log
p
[1+(p−1)n]•óêž,äT¥k{K
1,p
-š,…m
K
1,p
(T) =
p
m
−1
p
2
−1
.
y²:(i)Ø”m•n{pä(„ã4)ê,Kº:‡ên†êmƒmkXe'X:
n= p
0
+p
1
+p
2
+···+p
m−1
,=m= log
p
[1+(p−1)n].qd{pä½ÂŒ•∆(T) = 1+p,
¤±éu?¿˜ˆ{pä5`˜½kK
1,p
-š.
Ï•n= p
0
+p
1
+p
2
+···+p
m−1
= 1+(p
1
+1)+(p
2
−1)+···+(p
m−2
+1)+(p
m−1
−1), …x,
y©O•ÛêÚóêž,p
x
+1 = (p+1)(p
x−1
−p
x−2
+p
x−3
−···+1),p
y
−1 = (p+1)(p−1)(p
y −2
+
p
y−4
+···+1).¤±m•Ûêž,n
i
≡n
j
≡1(mod(p+1)),Ù¥n
i
=
p
m
i
−1
p−1
,n
j
=
p
m
j
−1
p−1
;m
i
,m
j
•?¿ü‡ØÓÛê.qÏ•K
1,p
-š¥•¹º:ê•p+1,¤±{K
1,p
-š¥Úº
:ê•n
0
= (p+1)m
K
1,p
(T),ù†n
i
≡n
j
≡1(mod(p+1))gñ.=m•Ûêž,{päÃ
{K
1,p
-š.
(ii)Ï•n= p
0
+p
1
+p
2
+···+p
m−1
=
p
m
−1
p−1
, m•óêž, Œ±Šn=
p
2k
−1
p−1
(Ù¥m= 2k,
k= 0,1,2,···),qÏ•
p
2k
−1
p−1
= (p+1)(p
0
+p
2
+p
4
+···+p
2k−2
),¤±(p+1)|
p
2k
−1
p−1
=(p+1)|n,
Ïd•3˜‡êq¦n=
p
m
−1
p−1
=(p+1)q,¤±Œ±•m•óêžn{p䘽
kq‡ØÓ•¹p+1‡º:f ã.qÏ•{päØ“f:z‡º:v
i
þ–†ØÓ
p‡º:ƒ…K
1,p
-š¥•¹º:ê•p+1,¤±m=log
p
[1+ (p−1)n]•óêžk
{K
1,p
-š.
nþŒ•{päT{K
1,p
-šêm
K
1,p
(T)†mƒmk±e'X:
m
K
1,p
(T) = p
0
+p
2
+p
4
+···+p
m−2
=
p
m
−1
p
2
−1
.

Figure5.PerfectbinarytreeT(wheregreenedgesdenote
byastarmatchingofT
ã5.{äT(Ù¥ÉÚ>“LT(š)
3{pä¥p= 2ž,Šâ½n2.6Œ±e¡íØ2.7µ
íØ2.7 -T´n‡º:{ä.Kéu?¿m= log
2
(1+n)(m∈N
∗
)k:
(i)m= log
2
(1+n)•Ûêž,äT¥vk{K
1,2
-š;
(ii)m= log
2
(1+n)•óêž,äT¥k{K
1,2
-š,…m
K
1,2
(T) =
2
m
−1
3
.
ã5(a)¥,m=4•óêž,w,k{K
1,2
-š;ã5(b)¥m=3•Ûêž,w,Ã
{K
1,2
-š.
DOI:10.12677/pm.2022.1281521397nØêÆ
o´
Ä7‘8
I[g,‰ÆÄ7‘8(No.11761070,61662079);2021c#õ‘Æg£«g,Ä7éÜ‘
8(2021D01C078);#õ“‰ŒÆ2020c˜6;’!2021c˜6‘§‘8]Ï.
ë•©z
[1]Hell,P.andKirkpatrick,D.G.(1986)PackingbyCompleteBipartiteGraphs.SIAMJournal
onAlgorithmDiscreteMathematics,7,199-209.https://doi.org/10.1137/0607024
[2]Lin,W. andLam,P.C.B. (2009)Star Matching andDistanceTwo Labelling. TaiwaneseJour-
nalofMathematics,13,211-224.https://doi.org/10.11650/twjm/1500405279
[3]o‰ä.ìè•†(š¯K[D]:[a¬Æ Ø©].H®:ÀHŒÆ,2019.
https://doi.org/10.27014/d.cnki.gdnau.2019.000170
[4]Û~†,4- .(šê†(ÃÎÒ).Ê.dAŠ[J].pA^êÆÆA6,2015,30(3):
333-339.
[5]„„, Û~†.'u(šêãUþe.[J].þ°nóŒÆÆ, 2020,42(4):317-319+367.
DOI:10.12677/pm.2022.1281521398nØêÆ

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