设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
A^
ê
Æ
?
Ð
,2022,11(3),1242-1246
PublishedOnlineMarch2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.113134
ä
Ú
´
¦
È
ã
‚
5
Î
Ý
ooo
±±±
ú
ô
“
‰
Œ
Æ
§
ê
Æ
†
O
Ž
Å
‰
ÆÆ
§
ú
ô
7
u
Â
v
F
Ï
µ
2022
c
2
21
F
¶
¹
^
F
Ï
µ
2022
c
3
16
F
¶
u
Ù
F
Ï
µ
2022
c
3
23
F
Á
‡
1970
c
Harary
J
Ñ
ã
‚
5
Î
Ý
V
g
,
•
´
ò
ã
G
>
8
©
)
¤
m
‡
>Ø
‚
5
Ü
•
ê
m
.
‚
5
Ü
=
z
˜
‡
ë
Ï
©
|
Ñ
´
´
ã
.
©
Ì
‡
é
ä
Ú
´
¦
È
(
?
1
?
Ø
,
Ï
L
é
¦
È
ã
¥
>
?
1
y
©
,
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
Hararyintroducedtheconceptoflineararboricityin
1970
.Thelineararboricityisthe
minimuminteger
m
suchthat
G
canbedecomposedinto
m
edge-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
c
Harary [1]
J
Ñ
ã
‚
5
Î
Ý
la
(
G
)
V
g
:
ò
ã
G
>
8
©
)
¤
>Ø
‚
5
Ü
•
ê
8
.
1980
c
,Akiyama,Exoo,Harary [2]
J
Ñ
ß
Ž
:
é
u
?
¿
K
ã
G
,
k
la
(
G
)=
d
∆(
G
)+1
2
e
.
Ï
•
é
u
?
¿
ã
G
,
k
la
(
G
)
≥d
∆(
G
)
2
e
;
é
u
?
¿
K
ã
G
,
k
la
(
G
)
≥d
∆(
G
)+1
2
e
,
Ï
dd
ß
Ž
d
u
Í
¶
‚
5
Î
Ý
ß
Ž
:
ß
Ž
1:
é
?
¿
ã
G
,
k
d
∆(
G
)
2
e≤
la
(
G
)
≤d
∆(
G
)+1
2
e
.
1980
c
,Akiyama,Exoo,Harary[2]
/
Ï
Vizing
0
s
½
n
y
²
3-
K
ã
Œ
±
©
)
¤
ü
‡
‚
5
Ü
,
Ó
ž
¦
‚
•
y
²
ä
,
ã
,
Ü
ã
÷
v
‚
5
Î
Ý
ß
Ž
.1981
c
,Akiyama,Exoo,
Harary [3]
/
Ï
u
Ï
f
©
)
•{
y
²
4-
K
ã
Œ
±
©
)
¤
n
‡
‚
5
Ü
.1982
c
,Tomasta [4]
y
²
∆= 6
ã
÷
v
‚
5
Î
Ý
ß
Ž
.1984
c
,Enomoto,P´
e
roche [5]
y
²
∆=5
,
6
,
8
ã
÷
v
‚
5
Î
Ý
ß
Ž
.1986
c
,Guldan [6]
y
²
∆=10
ã
÷
v
‚
5
Î
Ý
ß
Ž
.1999
c
,Wu [7]
y
²
e
G
´
∆
≥
9
²
¡
ã
,
K
G
÷
v
‚
5
Î
Ý
ß
Ž
.2008
c
,Wu [8]
<
y
²
e
G
´
∆=7
²
¡
ã
,
K
G
÷
v
‚
5
Î
Ý
ß
Ž
.
±
þ
(
J
y
²
¤
k
{
ü
²
¡
ã
Ñ
÷
v
‚
5
Î
Ý
ß
Ž
.
•
,
•
Œ
Ý
•
10
ã
,
²
¡
ã
ã
a
®
²
y
²
´
÷
v
‚
5
Î
Ý
ß
Ž
,
î
8
•
Ž
,
d
ß
Ž
„
v
k
y
²
.
3
©
¥
·
‚
Ì
‡
•
Ä
ä
Ú
´
¦
È
(
,
y
²
ä
Ú
´
¦
È
ã
÷
v
‚
5
Î
Ý
ß
Ž
,
ù
˜
(
J
´
L
d
ï
Ä
+
•
u
Ð
.
e
¡
·
‚
k
0
˜
¦
È
ã
ƒ
'
½
Â
.
½
Â
1.
é
u
ã
G
Ú
ã
H
,
ã
G
Ú
ã
H
(
k
È
ã
G
H
,
Ù
º:
8
Ü
•
V
(
G
)
×
V
(
H
),
X
J
3
G
H
¥
v
=
x
…
wy
∈
E
(
H
)
½
w
=
y
…
vx
∈
E
(
G
),
@
o
·
‚
¡
º:
(
v,w
)
Ú
(
x,y
)
ƒ
.
DOI:10.12677/aam.2022.1131341243
A^
ê
Æ
?
Ð
o
±
½
Â
2.
é
u
ã
G
Ú
ã
H
,
ã
G
Ú
ã
H
†
È
ã
G
×
H
,
Ù
º:
8
Ü
•
V
(
G
)
×
V
(
H
),
X
J
3
†
È
ã
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
3
1980
c
¤
'
u
ä
‚
5
Î
Ý
(
Ø
,
·
‚
y
²
ä
Ú
´
(
k
È
ã
,
†
È
ã
÷
v
‚
5
Î
Ý
ß
Ž
.
Ï
•
r
È
ã
´
(
k
È
ã
Ú
†
È
ã
¿
8
,
3
d
Ä
:
þ
,
·
‚
?
˜
Ú
y
²
ä
Ú
´
r
È
ã
÷
v
‚
5
Î
Ý
ß
Ž
,
±
e
½
n
.
½
n
1.
é
u
ä
T
Ú
´
P
n
r
È
ã
T
P
n
,
la
(
T
P
n
) =
d
∆(
T
P
n
)
2
e
.
2.
Ì
‡
(
J
9
y
²
1980
c
,Akiyama,Exoo,Harary
3
©
z
[2]
¥
Ø
=
y
²
ä
T
÷
v
‚
5
Î
Ý
ß
Ž
,
„
‰
Ñ
ä
T
‚
5
Î
Ý
°
(
Š
,
la
(
T
) =
d
∆(
T
)
2
e
.
•
©
Ù
5
,
3ù
p
·
‚
•[
¥
y
d
y
²
L
§
.
Ú
n
1.
[2]
X
J
ä
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
Ü
,
Ï
d
la
(
T
)
≤d
χ
0
(
T
)
2
e
=
d
∆(
T
)
2
e
.
n
þ
¤
ã
,
ä
T
‚
5
Î
Ý
la
(
T
) =
d
∆(
T
)
2
e
.
Ú
n
2.
é
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,
@
o
la
(
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
¥
>
?
1
y
©
.
X
J
(
k
È
ã
T
P
n
¥
>
´ä
T
¥
>
,
@
o
·
‚
ò
ù
>
˜
\
8
Ü
X
¥
,
–
¤
k
>
Ü
˜
\
X
¥
,
·
‚
X
¥
•
¹
n
+1
‡
ä
T
ë
Ï
©
|
,
…
ù
n
+1
‡
ë
Ï
©
|ƒ
m
´
üü
Ø
ƒ
.
d
ž
3
T
P
n
\
X
¥
,
Ù
z
˜
‡
ë
Ï
©
|
Ñ
´
´
P
n
,
…
T
P
n
\
X
¤
•
¹
ë
Ï
©
|
ê
•
ä
T
º:
ê
,
Ó
ž
T
P
n
\
X
ˆ‡
ë
Ï
©
|ƒ
m
•
´
üü
Ø
ƒ
,
Ï
d
T
P
n
\
X
÷
v
‚
5
Ü
½
Â
.
(
Ü
Ú
n
1,
·
‚
Œ
±
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
.
Ú
n
3.
é
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
Ú
n
1
Œ
,
ä
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.1131341244
A^
ê
Æ
?
Ð
o
±
e
¡
·
‚
Š
â
‚
5
Ü
LF
i
¥
>
œ
¹
5
é
†
È
ã
T
×
P
n
>
?
1
©
)
,
·
‚
•
e
u
s
u
t
∈
LF
i
,v
i
v
j
∈
P
n
,
@
o
3
†
È
ã
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
,
@
o
k
la
(
T
×
P
n
)
≤
2
la
(
T
),
Ï
d
†
È
ã
T
×
P
n
‚
5
Î
Ý
la
(
T
×
P
n
)
≤
2
la
(
T
)
≤
2
d
∆(
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
¤
«
,
·
‚
r
K
3
º:
P
Š
{
u
1
,u
2
,u
3
,u
4
}
,
r
P
2
º:
P
Š
{
v
1
,v
2
,v
3
}
,
r
K
3
>
P
Š
{
u
1
u
2
,u
1
u
3
,u
1
u
4
}
,
r
P
2
>
P
Š
{
v
1
v
2
,v
2
v
3
}
.
Figure1.
Thedirectproductof
K
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
Ü
©
O
P
Š
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
ƒ
A
y
©
,
=
†
È
ã
K
3
×
P
2
>
Œ
±
U
ì
±
e
•
ª
5
?
1
y
©
µ
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
)
≤
2
la
(
K
3
)
≤
2
d
∆(
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
.
½
n
1.
é
u
ä
T
Ú
´
P
n
r
È
ã
T
P
n
,
la
(
T
P
n
) =
d
∆(
T
P
n
)
2
e
.
y
²
.
·
‚
•
r
È
ã
´
(
k
È
ã
Ú
†
È
ã
¿
,
@
o
d
r
È
ã
½
Â
Œ
,∆(
T
P
n
)=
∆(
T
P
n
)+∆(
T
×
P
n
) = (∆(
T
)+2)+2∆(
T
) = 3∆(
T
)+2.
DOI:10.12677/aam.2022.1131341245
A^
ê
Æ
?
Ð
o
±
d
ã
‚
5
Î
ݽ
Â
Œ
,
la
(
T
P
n
)
≥d
∆(
T
P
n
)
2
e
=
d
3∆(
T
)+2
2
e
.
d
Ú
n
2
Ú
Ú
n
3
Œ
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
(
1980
c
,Akiyama, Exoo,Harary
J
Ñ
‚
5
Î
Ý
ß
Ž
,40
õ
c
5
,
d
ß
Ž
˜
†
Ñ
´
ã
Ø
¥
2
•
É
'
5
9
:
{
K
ƒ
˜
,
¯
õ
Æ
ö
Ý
u
d
ß
Ž
ï
Ä
¿
•
d
‰
Ñ
-
Œ
z
,
î
8
•
Ž
,
•
Œ
Ý
•
10
ã
!
²
¡
ã
!
X
²
1
ã
ã
a
®
²
y
²
´
÷
v
‚
5
Î
Ý
ß
Ž
,
d
ß
Ž
„
v
k
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:2
h
129::AID-JGT5
i
3.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.1131341246
A^
ê
Æ
?
Ð