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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2022,11(3),1242-1246
PublishedOnlineMarch2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.113134
äÚ´¦Èã‚5ÎÝ
ooo±±±
úô“‰ŒÆ§êƆOŽÅ‰ÆÆ§úô7u
ÂvFϵ2022c221F¶¹^Fϵ2022c316F¶uÙFϵ2022c323F
Á‡
1970 cHararyJÑã‚5ÎÝVg,•´òãG>8©)¤m‡>Ø‚5Ü
•êm.‚5Ü=z˜‡ëÏ©|Ñ´´ã.©Ì‡éäÚ´¦È(?1?Ø,Ï
Lé¦Èã¥>?1y©,y²äÚ´(kÈã!†Èã!rÈã÷v‚5ÎÝߎ"
'…c
‚5ÎÝߎ§(kÈ㧆Èã§rÈã
TheLinearArboricityoftheProduct
ofTreeandPath
PingLi
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Feb.21
st
,2022;accepted:Mar.16
th
,2022;published:Mar.23
rd
,2022
Abstract
Hararyintroducedtheconceptoflineararboricityin1970.Thelineararboricityisthe
minimumintegermsuchthatGcanbedecomposedintomedge-disjointlinearforests.
Alinearforestisagraphinwhicheveryconnectedcomponentisapath.Wediscuss
©ÙÚ^:o±.äÚ´¦Èã‚5ÎÝ[J].A^êÆ?Ð,2022,11(3):1242-1246.
DOI:10.12677/aam.2022.113134
o±
theproductstructureoftreeandpath,dividetheedgesintheproductgraphand
provethatthelineararboricityconjectureholdsforthecartesianproduct,thedirect
product,thestrongproductoftreeandpath.
Keywords
LinearArboricityConjecture,TheCartesianProductofGraphs,TheDirectProduct
ofGraphs,TheStrongProductofGraphs
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.Úó
©•ïÄ{üÕã,éu?¿‰½ãG,·‚^V(G),E(G) Ú∆(G) ©OL«ãG
º:8Ü,>8ÜÚ•ŒÝ.‚5Ü=z˜‡ëÏ©|Ñ´´ã.1970 cHarary [1] JÑã
‚5ÎÝla(G) Vg:òãG>8©)¤>Ø‚5Ü•ê8.
1980 c,Akiyama,Exoo,Harary [2] JÑߎ:éu?¿KãG,kla(G)=d
∆(G)+1
2
e.
Ï•éu?¿ãG,kla(G)≥d
∆(G)
2
e;éu?¿KãG,kla(G)≥d
∆(G)+1
2
e,Ïddß
ŽduͶ‚5ÎÝߎ:
ߎ1:é?¿ãG,kd
∆(G)
2
e≤la(G) ≤d
∆(G)+1
2
e.
1980c,Akiyama,Exoo,Harary[2]/ÏVizing
0
s½ny²3-K㌱©)¤ü‡‚
5Ü,Óž¦‚•y²ä,ã,Üã÷v‚5ÎÝߎ.1981c,Akiyama,Exoo,
Harary [3]/ÏuÏf©)•{y²4-K㌱©)¤ n‡‚5Ü.1982 c,Tomasta [4]
y²∆= 6 ã÷v‚5ÎÝߎ.1984 c,Enomoto,P´eroche [5]y²∆=5,6,8 ã÷v
‚5ÎÝߎ.1986 c,Guldan [6] y²∆=10ã÷v‚5ÎÝߎ.1999 c,Wu [7] y²
eG´∆≥9 ²¡ã,KG÷v‚5ÎÝߎ.2008 c,Wu [8]<y²eG´∆=7 ²
¡ã,KG÷v‚5ÎÝߎ.±þ(Jy²¤k{ü²¡ãÑ÷v‚5ÎÝߎ.
•,•ŒÝ•10 ã,²¡ããa®²y²´÷v‚5ÎÝߎ,î8•Ž,dߎ
„vky².3©¥·‚̇•ÄäÚ´¦È(,y²äÚ´¦ Èã÷v‚5Î
Ýߎ,ù˜(J´LdïÄ+•uÐ.
e¡·‚k0˜¦Èãƒ'½Â.
½Â1.éuãGÚãH,ãGÚãH(kÈãGH,Ùº:8Ü•V(G)×V(H),X
J3GH¥v= x…wy∈E(H) ½w= y…vx∈E(G),@o·‚¡º:(v,w)Ú(x,y) ƒ.
DOI:10.12677/aam.2022.1131341243A^êÆ?Ð
o±
½Â2.éuãGÚãH,ãGÚãH†ÈãG×H,Ùº:8Ü•V(G)×V(H),XJ3
†ÈãG×H¥vx∈E(G) …wy∈E(H),@o·‚¡º:(v,w)Ú(x,y)ƒ.
½Â3.éuãGÚãH,ãGÚãHrÈãGH,§´(kÈãGHÚ†Èã
G×H¿8.
©Ì‡éäÚ´¦È(?1ïÄ,/ÏAkiyama,Exoo,Harary 31980c¤'u
ä‚5ÎÝ(Ø,·‚y²äÚ´(kÈã,†Èã÷v‚5ÎÝߎ.Ï•rÈã´(
kÈãÚ†Èã¿8,3dÄ:þ,·‚?˜Úy²äÚ´rÈã÷v‚5ÎÝߎ,
±e½n.
½n1.éuäTÚ´P
n
rÈãTP
n
,la(TP
n
) = d
∆(TP
n
)
2
e.
2.̇(J9y²
1980c,Akiyama,Exoo,Harary3©z[2]¥Ø=y²äT÷v‚5ÎÝߎ,„‰Ñä
T‚5ÎÝ°(Š,la(T) = d
∆(T)
2
e.•©Ù5,3ùp·‚•[¥ydy²L§.
Ún1.[2]XJäT•ŒÝ•∆(T),@oäT‚5ÎÝla(T) = d
∆(T)
2
e.
y².dã‚5ÎÝ½ÂŒla(T) ≥d
∆(T)
2
e.
Ï•äT•ŒÝ•∆(T),§>Úêχ
0
(T)=∆(T),äT¥?¿ü«ôÚ>ÑfãÑ
¬/¤˜‡‚5Ü,Ïdla(T) ≤d
χ
0
(T)
2
e= d
∆(T)
2
e.
nþ¤ã,äT‚5ÎÝla(T) = d
∆(T)
2
e.
Ún2.éuäTÚ´P
n
(kÈãTP
n
,la(TP
n
) = d
∆(TP
n
)
2
e.
y².Šâ(kÈã½Â, ·‚•3(kÈãTP
n
¥, •ŒÝ∆(TP
n
) = ∆(T)+2,
@ola(TP
n
)≥d
∆(TP
n
)
2
e=d
∆(T)+2
2
e. e¡·‚Uì(kÈãTP
n
¥>´Ä•äT¥
>,5é(kÈãTP
n
¥>?1y©.
XJ(kÈãTP
n
¥>´äT¥>,@o·‚òù>˜\8ÜX¥,–¤k>
ܘ\X¥,·‚X¥•¹n+1 ‡äTëÏ©|,…ùn+1 ‡ëÏ©|ƒm´üüØ
ƒ.dž3TP
n
\X¥,Ùz˜‡ëÏ©|Ñ´´P
n
,…TP
n
\X¤•¹ëÏ©|ê
•äTº:ê,ÓžTP
n
\Xˆ‡ëÏ©|ƒm•´üü؃,ÏdTP
n
\X÷v‚
5Ü½Â.
(ÜÚn1,·‚Œ±la(TP
n
) ≤la(T)+la(P
n
) = d
∆(T)
2
e+1 = d
∆(T)+2
2
e= d
∆(TP
n
)
2
e.
nþ¤ã,äTÚ´P
n
(kÈãTP
n
‚5ÎÝla(TP
n
) = d
∆(TP
n
)
2
e.
Ún3.éuäTÚ´P
n
†ÈãT×P
n
,la(T×P
n
) = d
∆(T×P
n
)
2
e.
y².d†Èã½ÂŒ,†ÈãT×P
n
•ŒÝ∆(T×P
n
) = 2∆(T).
dã‚5ÎÝ½ÂŒ•,†ÈãT×P
n
‚5ÎÝla(T×P
n
) ≥d
∆(T×P
n
)
2
e= d
2∆(T)
2
e=
d∆(T)e.dÚn1 Œ,äT‚5ÎÝla(T)=d
∆(T)
2
e,=äTŒ±d
∆(T)
2
e‡‚ 5ÜCX,
·‚räT¤©)¤‚5ÜPŠLF
i
,Ù¥i∈{1,2,...,d
∆(T)
2
e}.
DOI:10.12677/aam.2022.1131341244A^êÆ?Ð
o±
e¡·‚Šâ‚5ÜLF
i
¥>œ¹5é†ÈãT×P
n
>?1©),·‚•e
u
s
u
t
∈LF
i
,v
i
v
j
∈P
n
, @o3†ÈãT×P
n
¥, k(u
s
,v
i
)(u
t
,v
j
) ∈T×P
n
,(u
s
,v
j
)(u
t
,v
i
) ∈T×P
n
.
3é†ÈãT×P
n
>©)L§¥,·‚ò†ÈãT×P
n
¥>(u
s
,v
i
)(u
t
,v
j
) Ú(u
s
,v
j
)(u
t
,v
i
)
˜\ØÓ‚5Ü¥,=(u
s
,v
i
)(u
t
,v
j
) ∈LF
1
i
,(u
s
,v
j
)(u
t
,v
i
) ∈LF
2
i
,Ù¥LF
1
i
6= LF
2
i
,@ok
la(T×P
n
) ≤2la(T),Ïd†ÈãT×P
n
‚5ÎÝla(T×P
n
) ≤2la(T) ≤2d
∆(T)
2
e= d∆(T)e.
nþ¤ã,†ÈãT×P
n
‚5ÎÝla(T×P
n
) = d∆(T)e= d
∆(T×P
n
)
2
e.
e¡·‚±†ÈãK
3
×P
2
•~5?1äN`².Xã1¤«,·‚rK
3
º:PŠ
{u
1
,u
2
,u
3
,u
4
},rP
2
º:PŠ{v
1
,v
2
,v
3
},rK
3
>PŠ{u
1
u
2
,u
1
u
3
,u
1
u
4
},rP
2
>PŠ
{v
1
v
2
,v
2
v
3
}.
Figure1.ThedirectproductofK
3
×P
2
ã1.†ÈãK
3
×P
2
3†ÈãK
3
×P
2
¥,∆(K
3
×P
2
) = 2∆(K
3
) = 6,†ÈãK
3
×P
2
¤•¹>k
{(u
1
,v
1
)(u
2
,v
2
),(u
1
,v
1
)(u
3
,v
2
),(u
1
,v
1
)(u
4
,v
2
);
(u
1
,v
2
)(u
2
,v
1
),(u
1
,v
2
)(u
3
,v
1
),(u
1
,v
2
)(u
4
,v
1
);
(u
1
,v
2
)(u
2
,v
3
),(u
1
,v
2
)(u
3
,v
3
),(u
1
,v
2
)(u
4
,v
3
);
(u
1
,v
3
)(u
2
,v
2
),(u
1
,v
3
)(u
3
,v
2
),(u
1
,v
3
)(u
4
,v
2
)}.
Ï•∆(K
3
) =3,la(K
3
) =2,K
3
Œ±ü‡‚5Ü¤CX,••Bå„,·‚rùü‡‚5
Ü©OPŠLF
1
ÚLF
2
,·‚r{u
1
u
2
,u
1
u
3
}wŠ‚5ÜLF
1
¥>,r{u
1
u
4
}wŠ‚5Ü
LF
2
¥>,´P
2
¥>•{v
1
v
2
,v
2
v
3
},e¡·‚Œ±ò†ÈãK
3
×P
2
>UìäT¥‚5
ÜCX•ª5?1ƒAy©,=†ÈãK
3
×P
2
>Œ±Uì±e•ª5?1y©µ
A
1
= {(u
1
,v
1
)(u
2
,v
2
),(u
1
,v
1
)(u
3
,v
2
),(u
1
,v
2
)(u
2
,v
3
),(u
1
,v
2
)(u
3
,v
3
)}.
A
2
= {(u
1
,v
2
)(u
2
,v
1
),(u
1
,v
2
)(u
3
,v
1
),(u
1
,v
3
)(u
2
,v
2
),(u
1
,v
3
)(u
3
,v
2
)}.
A
3
= {(u
1
,v
1
)(u
4
,v
2
),(u
1
,v
2
)(u
4
,v
1
),(u
1
,v
2
)(u
4
,v
3
),(u
1
,v
3
)(u
4
,v
2
)}.
ò†ÈãK
3
×P
2
>²Lùy©ƒ,·‚Œ±A
1
,A
2
,A
3
þ•‚5Ü,Ïd
la(K
3
×P
2
) ≤2la(K
3
) ≤2d
∆(K
3
)
2
e= d
∆(K
3
×P
2
)
2
e.
dã‚5ÎÝ½ÂŒ,la(K
3
×P
2
) ≥d
∆(K
3
×P
2
)
2
e.
nþ¤ã,la(K
3
×P
2
) = d
∆(K
3
×P
2
)
2
e.
½n1.éuäTÚ´P
n
rÈãTP
n
,la(TP
n
) = d
∆(TP
n
)
2
e.
y².·‚•rÈã´(kÈãÚ†Èã¿,@odrÈã½ÂŒ,∆(TP
n
)=
∆(TP
n
)+∆(T×P
n
) = (∆(T)+2)+2∆(T) = 3∆(T)+2.
DOI:10.12677/aam.2022.1131341245A^êÆ?Ð
o±
dã‚5ÎÝ½ÂŒ,la(TP
n
) ≥d
∆(TP
n
)
2
e= d
3∆(T)+2
2
e.
dÚn2 ÚÚn3 Œla(∆(TP
n
))+la(∆(T×P
n
)) =d
∆(T)+2
2
e+∆(T)= d
3∆(T)+2
2
e,¤±
la(∆(TP
n
)) ≤la(∆(TP
n
))+la(∆(T×P
n
)) = d
3∆(T)+2
2
e.
nþ¤ã,äTÚ´P
n
rÈãTP
n
‚5ÎÝla(TP
n
) = d
3∆(T)+2
2
e= d
∆(TP
n
)
2
e.
3.o(
1980c,Akiyama, Exoo,HararyJÑ‚5ÎÝߎ,40õc5,dߎ˜†Ñ´ãØ¥2•
É'59:{Kƒ˜,¯õÆöÝudߎïÄ¿•d‰Ñ-Œz,î8•Ž,•ŒÝ•
10ã!²¡ã!X²1ããa®²y²´÷v‚5ÎÝߎ,dߎ„vky
².©·‚ ÏLéäÚ´¦È(?1ïÄ,y²äÚ´(kÈã!†Èã!rÈãÑ
÷v‚5ÎÝߎ,´LdïÄ+•ïÄ(J.
ë•©z
[1]Harary,F.(1970)CoveringandPackinginGraphs.AnnalsoftheNewYorkAcademyof
Sciences,175,198-215.https://doi.org/10.1111/j.1749-6632.1970.tb56470.x
[2]Akiyama,J.,Exoo,G.andHarary,F.(1980)CoveringandPackinginGraphsIII:Cyclicand
AcyclicInvariants.MathematicaSlovaca,30,405-417.
[3]Akiyama,J.,Exoo,G.andHarary,F.(1981)CoveringandPackinginGraphsIV:Linear
Arboricity.Networks,11,69-72.https://doi.org/10.1002/net.3230110108
[4]Tomasta,P.(1982)NoteonLinearArboricity.MathematicaSlovaca,32,239-242.
[5]Enomoto,H.andP´eroche,B.(1984)The LinearArboricityofSomeRegularGraphs.Journal
ofGraphTheory,8,309-324.https://doi.org/10.1002/jgt.3190080211
[6]Guldan,F.(1986)TheLinearArboricityof10-RegularGraphs.MathematicaSlovaca,36,
225-228.https://doi.org/10.1002/jgt.3190100408
[7]Wu,J.(1999)OntheLinearArboricityofPlanarGraphs.JournalofGraphTheory,31,
129-134.https://doi.org/10.1002/(SICI)1097-0118(199906)31:2h129::AID-JGT5i3.0.CO;2-A
[8]Wu,J. and Wu, Y.(2008) The LinearArboricity ofPlanarGraphsof Maximum DegreeSeven
IsFour.JournalofGraphTheory,58,210-220.https://doi.org/10.1002/jgt.20305
DOI:10.12677/aam.2022.1131341246A^êÆ?Ð

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