设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
A^
ê
Æ
?
Ð
,2021,10(11),4056-4064
PublishedOnlineNovemb er2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.1011431
²
¡
4
·
8
2
‚
f
ã
ž
“
¯
K
000
ƒƒƒ
•••
1
∗
§§§
>>>
ùùù
1
†
§§§
uuu
°°°
2
§§§
ŸŸŸ
www
AAA
1
1
#
õ
“
‰
Œ
Æ
ê
Æ
‰
ÆÆ
§
#
õ
¿
°
7
à
2
#
õ
Œ
Æ
ê
Æ
†
X
Ú
‰
ÆÆ
§
#
õ
¿
°
7
à
Â
v
F
Ï
µ
2021
c
10
23
F
¶
¹
^
F
Ï
µ
2021
c
11
13
F
¶
u
Ù
F
Ï
µ
2021
c
11
29
F
Á
‡
ž
“
¯
K
(FirefighterProblem)
´
˜
‡
l
Ñ
Ä
D
Â
.
§
†
¼
œ
›
›
!
‚
ó
D
Â
!
Ü
“
»
¢
S
¯
K
—
ƒ
ƒ
'
§
§
•
@
´
d
Í
¶
O
Ž
Å
n
Ø
Æ
[
Hartnell
3
1995
c
1
25
3
|
Ü
ê
Æ
†
O
Ž
Œ
¬
þ
Ä
g
J
Ñ
"
-
G
=(
V
(
G
)
,E
(
G
))
´
n
(
n
≥
2)
‡
º:
ë
Ïã
"
b
»
3
ã
G
¥
?
¿˜
‡
º:
v
?
-
å
§
ž
“
K
À
J
™
X
»
º:
o
(
˜
,
‡
º:
o
§
K3
‡
L
§
¥
Ñ
ò
?
u
o
G
)
§
,
»
ø
ò
v
™
\
o
…
v
X
»
:
"
•
g
e
§
»
Ú
ž
“
O
/
3
ã
G
þ
£
Ä
,
†
»
Ø
U
U
Y
ø
ò
§
‡
L
§
(
å
§
ž
“
?
Ö
´¦
•
¼
Í
:
ê
•
õ
"
-
sn
(
v
)
L
«
ã
G
¥
º:
v
Š
•
»
:
ž
˜
‡
ž
“
¤
U
o
•
õº:
ê
"
ã
G
•
¹
Ç
ρ
(
G
)
½
Â
•
P
v
∈
V
(
G
)
sn
(
v
)
n
2
§
=
»
‘
Å
/
3
ã
G
˜
‡
º:
-
å
ž
§
˜
‡
ž
“
•
õ
U
o
º:
ê
²
þ
Š
"
©
Ä
k
ï
Ä
k
•
²
¡
4
·
8
2
‚
f
ã
•
¹
Ç
§
©
Û
‚
f
ã
¥
:
•
¹
ê
C
z
5
Æ
¿
‰
Ñ
k
•
4
·
8
2
‚
f
ã
•
¹
Ç
(
ƒ
Š
¶
l
y
²
é
u
Ã
•
²
¡
4
·
8
2
‚
f
ã
§
z
‡
£
Ü
¦
^
˜
‡
ž
“
²
L
k
•
g
o
Œ
±
›
›
»
ø
ò
"
'
…
c
ž
“
¯
K
§
•
¹
ê
§
•
¹
Ç
§
²
¡
4
·
8
2
‚
f
ã
TheFirefighterProblemofPlane
4
·
8
2
Grids
∗
1
˜
Š
ö
"
†
Ï
Õ
Š
ö
"
©
Ù
Ú
^
:
0
ƒ
•
,
>
ù
,
u
°
,
Ÿ
w
A
.
²
¡
4
·
8
2
‚
f
ã
ž
“
¯
K
[J].
A^
ê
Æ
?
Ð
,2021,10(11):
4056-4064.DOI:10.12677/aam.2021.1011431
0
ƒ
•
ZhiyaoXing
1
∗
,HongBian
1
†
,HaizhengYu
2
,LinaWei
1
1
SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Oct.23
rd
,2021;accepted:Nov.13
th
,2021;published:Nov.29
th
,2021
Abstract
Firefighter Problem canbeviewed asadiscretedynamicpropagationmodel,whichis
closelyrelatedtothepropagationofviruses,rumoursorepidemics.FirefighterProb-
lemwasintroducedbyHartnellatthe25thManitobaConferenceonCombinatorial
MathematicsandComputing.Let
G
be aconnectedgraphwith
n
(
n
≥
2)
vertices.As-
sumethatafirebreaksoutatavertex
v
of
G
,afirefighter (ordefender)choosesaset
ofverticesnotyetonfiretoprotect;onceavertexhasbeen chosenby thefirefighter,
it isconsideredprotectedorsafe fromany further movesofthe fire.The process ends
when the firecanno longerspread.Let
sn
(
v
)
denote the maximum number ofvertices
in
G
thatthefirefightercansavewhenafirebreaksoutatvertex
v
,whichcanbe
referredtoasthesurvivingnumberfor
v
.Thesurvivingrate
ρ
(
G
)
ofgraph
G
isde-
finedtobetheaveragepercentageofvertices thatcanbesaved whenafirerandomly
breaksoutatonevertexofgraph,
i.e.
,
P
v
∈
V
(
G
)
sn
(
v
)
n
2
.Inthispaper,wefirstlystudythe
survivingrateoffinite
4
·
8
2
grids,andpresenttheexactvalueofthesurvivingrate
offinite
4
·
8
2
grids.Moreover,weprovethatwhenfirebreaksoutatanyvertexin
infinite
4
·
8
2
grids,usingonefirefighterineachturncancontrolthespreadofafire
afteralimitedamountofprotection.
Keywords
FirefightersProblem,SurvivingNumber,SurvivingRate,Plane
4
·
8
2
GridsGraph
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.10114314057
A^
ê
Æ
?
Ð
0
ƒ
•
1.
Ú
ó
#
)
¡
ö
(COVID-19)
Œ
6
1
2
•
@
•
´
y
“
š
Æ
¤
þ
¡
•
ˆ
9
)
·
¯
K
,
§
3
6
Ï
-
.
ˆ
/
<
a
è
x
Ú
²
L
.
§
å
•
™
k
½
Ø
,
®
×
„
3
I
S
!
ø
ò
.
–
2020
c
4
3
F
,
¥
(
¾
~
•
1,116,643
~
,
Ù
¥
•
)
59,158
~
k
(
Š
â
-
.
¤
L
&
E
).
Ž
8
c
,
Ñ
„
v
k
é
ù
«
#
;
¾
ä
NA
†
Ô
.
ž
“
¯
K
(FirefighterProblem)
´
˜
‡
l
Ñ
Ä
D
Â
.
,
†
¼
œ
›
›
!
‚
ó
D
Â
!
Ü
“
»
¢
S
¯
K
—
ƒ
ƒ
'
,
§
•
@
´
d
Í
¶
O
Ž
Å
n
Ø
Æ
[
Hartnell
3
1995
c
1
25
3
|
Ü
ê
Æ
†
O
Ž
Œ
¬
þ
Ä
g
J
Ñ
[1].
b
3
ž
m
t
=0
ž
•
,
ã
G
= (
V
(
G
)
,E
(
G
))
¥
?
¿˜
‡
º:
v
Š
•
»
:
,
é
u
z
˜
‡
ü
ž
m
(
i,i
+1],
i
≥
0,
˜
‡
ž
“
o
˜
‡
™
-
:
(
ù
‡
:
˜
o
,
K3
‡
L
§
¥
Ñ
ò
?
u
o
G
),
,
»
ø
ò
v
™
\
o
…
v
k
X
»
:
.
•
g
e
,
»
Ú
ž
“
O
/
3
ã
G
þ
£
Ä
,
†
»
Ø
U
U
Y
ø
ò
,
‡
L
§
(
å
.
•
,
ã
G
¥
º:
k
n
«
G
,
©
O
´
X
º:
!
o
º:
Ú
Q
v
k
X
•
v
k
o
º:
,
v
k
X
:
¡
•
¼
Í
:
.
du
3
‡
L
§
¥
,
•
k
ž
“
k
Z
ý
ü
Ñ
,
»
¿
v
k
æ
ü
Ñ
,
§
•
´
ø
ò
§
:
,
¤
±
ž
“
¯
K
•
Œ
±
w
¤
´
˜
‡
<
|
Ü
i
Z
.
D
Ú
6
1
¾
.
Ñ
´
b
+
N
ƒ
m
´
ƒ
p·
,
,
‡
N
ƒ
m
ƒ
p
é
X
¿
…
Œ
±
r
;
¾
D
Â
‰
*
d
.
,
,
•
C
6
1
¾
Æ
[
Á
ã
ò
˜
m
&
E
•
•
¹
3
¦
‚
.
¥
.
Ï
d
,
ž
“
¯
K
3
,
«
¿Â
þ
Œ
±
w
¤
v
k
£
•
#
)
;
¾
D
Â
.
.
¯¢
þ
,
du
3
y
¢)
¹
¥
k
¼
¢
´
k
•
¿
…
¼
¢
+
n
<
•
´
k
•
,
Ï
d
,
z
˜
Ú
•
#
N
k
•
‡
v
k
a
/
<
«
¼
¢
.
@
o
˜
‡
é
g
,
¯
K
Ò
´
X
Û
«
¦
•
a
/
<
ê
ˆ
•
º
g
Hartnell
J
Ñ
ž
“
¯
K
,
N
õ
û
)
V
g
Ú
¯
K
ƒ
U
J
Ñ
.2009
c
‘
…
<
[2]
Ç
k
Ú
\
ã
•
¹
Ç
V
g
,
¿
é
ä
!
Œ
²
¡
ã
ÚM
ã
A
Ï
ã
a
ï
Ä
ü
<
“
»
¯
K
.
-
sn
(
v
)
L
«
3
ã
G
¥
:
v
Š
•
»
:
˜
‡
ž
“
3
‡
o
L
§
(
å
Œ
±
o
:
•
õº:
ê
,
¡
•
:
v
•
¹
ê
.
d
d
,
ã
G
•
¹
ê
sn
(
G
)
½
Â
•
»
‘
Å
/
3
ã
G
¥
?
¿˜
‡
º:
u
ž
,
˜
‡
ž
“
•
õ
Œ
±
o
º:
ê
,
=
sn
(
G
)=
P
v
∈
V
(
G
)
sn
(
v
).
ã
G
•
¹
Ç
½
Â
X
e
:
ρ
(
G
) =
sn
(
V
(
G
))
n
2
,
L
«
˜
‡
ž
“
•
õ
Œ
±
o
²
þ
º:
ê
.
k
´
ê
,
k
-
ž
“
¯
K
Ò
´
‡
¦
ž
“
z
˜
Ú
o
k
‡
™
\
“
o
…
v
k
X
:
,
†
»
Ø
2
ø
ò
‡
L
§
(
å
(
=
e
˜
‡
ž
“
À
J
˜
‡
º:
?
1
“
o
,
K
z
˜
Ú
I
‡
k
‡
ž
“
).
a
q
/
,
^
sn
k
(
v
)
L
«
ã
G
¥
º:
v
Š
•
»
:
ž
^
k
‡
ž
“
•
õ
Œ
±
o
º:
ê
.
ã
G
k
-
•
¹
ê
sn
k
(
G
)
½
Â
•
‘
Å
/
À
J
G
¥
,
‡
:
•
»
:
,
@
o
k
‡
ž
“
•
õ
Œ
±
o
º:
ê
,
=
sn
k
(
G
)=
P
v
∈
V
(
G
)
sn
k
(
v
),
ã
G
k
-
•
¹
½
Â
•
:
ρ
k
(
G
)=
sn
k
(
V
(
G
))
n
2
.
w
,
,
k
-
ž
“
¯
K
´
ž
“
¯
K
í
2
.
3
Ø
Óã
a
ž
“
¯
K
ƒ
U
ï
Ä
.
3
1995
c
Hartnell
<
3
©
z
[1]
Ò
®
²
y
²
é
u
Ü
ã
ž
“
¯
K
´
NP
-
¯
K
.Ng
Ú
Raff
3
2008
c
[3]
y
²
,
X
J
Œ
^
ž
“
ê
þ
3
ž
m
t
¥
´
±
Ï
5
C
z
,
¿
…
z
‡
ž
m
±
Ï
²
þ
ž
“
‡
ê
Œ
u
3
2
,
@
o
é
u
‘Ã
•
‚
f
ã
¥
,
?
¿
k
•
‡
º:
m
©
-
»
/
Ñ
Œ
±
›
›
.2010
c
Finbow
<
[4]
&
Ä
X
e
A
Ï
ã
•
¹
Ç
,
X
:
²
¡
ã
!
Œ
•
'
Œ
²
¡
ã
,
Ø
¹
K
4
minor
f
ª
ã
Ú
d
-
ò
z
ã
,
¿
y
²
X
e
(
J
:
1)
A
¤
k
ã
k
-
•
¹
Ç
?
¿
ª
u
0.
2)
é
u
Œ
•
–
´
9
²
¡
ã
G
,
k
ρ
(
G
)
≥
2
35
.
DOI:10.12677/aam.2021.10114314058
A^
ê
Æ
?
Ð
0
ƒ
•
3)
é
u
Ø
¹
K
4
minor
f
ª
ã
,
k
ρ
2
(
G
)
≥
1
16
.
4)
é
u
d
-
ò
z
ã
G
,
k
ρ
2
d
−
1
(
G
)
≥
2
5
d
.
5)
é
u
²
¡
ã
G
,
k
ρ
5
(
G
)
≥
2
15
.
3
2017
c
Adjiashvili
<
[5]
ï
Ä
ê
ž
“
¯
K
Ú
]
•
“
»
›
›
¯
K
,
¿
y
²
é
u
ä
ž
“
¯
K
k
˜
‡
PTAS
Ž
{
.
©
Ì
‡
ï
Ä
²
¡
4
·
8
2
‚
f
ã
ž
“
¯
K
.
Ä
k
ï
Ä
k
•
²
¡
4
·
8
2
‚
f
ã
•
¹
Ç
,
©
Û
‚
f
ã
¥
:
•
¹
ê
C
z
5
Æ
¿
‰
Ñ
k
•
4
·
8
2
‚
f
ã
•
¹
Ç
(
ƒ
Š
,
l
y
²
é
u
Ã
•
²
¡
4
·
8
2
‚
f
ã
,
z
‡
£
Ü
¦
^
˜
‡
ž
“
²
L
k
•
g
o
Œ
±
›
›
»
ø
ò
.
2.
Ì
‡
(
J
2.1.
k
•
4
·
8
2
‚
f
ã
2000
c
,Shrock
Ú
Wu
3
©
z
[6]
‰
Ñ
²
¡
4
·
8
2
‚
f
G
t
(
n,m
)
)
¤
êê
8
Ú
ì
?
~
ê
O
Ž
ú
ª
.
!
¥
Ä
u
²
¡
4
·
8
2
‚
f
ã
•
Ä
3
k
•
œ
¹
e
?
¿˜
‡
:
Š
•
å
©
»
:
¿
…
z
‡
£
Ü
•
^
˜
‡
ž
“
o
Ù
¦
:
.
G
t
(
n,m
)
¥
m
L
«
•
/
ê
,
n
L
«
z
•
/
‡
ê
,
Š
â
ã
E
Œ
±
w
Ñ
z
˜
l
>
/
‡
ê
•
n
+ 1.
-
l
L
«
:
ê
,
Œ
±
'
X
ª
l
=3
m
+4.
N
´
w
Ñ
ù
a
‚
f
ã
´
d
˜
l
>
/
Ê
b
|
¤
,
ã
¥•
k
Ý
½
ö
n
Ý:
,
¿
…
Ê
b
a
.
†
8
‚
f
ã
a
q
,
Ê
b
•
ª
X
ã
1
¤
«
:
Figure1.
Thegridgraph
G
t
(4
,
1)
ã
1.
G
t
(4
,
1)
‚
f
ã
Ú
n
2.1
é
uk
•
²
¡
4
·
8
2
‚
f
,
'
Ð
o
ü
Ñ
Ò
´
ž
“
o
:
/
¤
˜
‡
•
Œ
C
.
y
²
Ï
•
•
Ä
´
k
•
‚
f
ã
,
¤
±
ã
´
k
>
.
.
Š
â
•
r
“
»
p
©
•
À
Ü
!
Ü
Ü
!
H
Ü
!
Ü
.
•
ª
8
´
^
“
»
p
Ú
‚
f
ã
>
.
-
Ü
/
¤
˜
‡
•
Œ
C
.
3
t
=0
ž
b
»
u
3
ã
G
¥
?
¿˜
‡
:
v
;
t
= 1
ž
ž
“
À
J
v
?
˜
:
o
¦
ž
“
3
»
C
˜
;
t
=2
ž
»
ø
ò
:
v
v
k
o
Ú
v
k
-
:
.
˜
˜
ž
“
3
Ü
·
˜
þ
•
(
ù
ž
“
é
›
›
»
ø
ò
´
k
/
.
U
Y
þ
ã
L
§
,
†
ž
“
o
:
|
¤
“
»
p
†
‚
f
ã
>
.
-
Ü
3
˜
å
/
¤
˜
‡
•
Œ
C
,
@
o
»
ò
Ø
2
ø
ò
.
X
ã
2
¥
,
:
>
ê
i
L
«
3
ž
m
t
=0,1,2,
···
,9
é
ù
‡
:
¤
?
1
ö
Š
.
ã
¥
ù
Ú
:
L
«
»
ø
ò
:
(
Ù
¥
I
Ò
•
0
ù
Ú
:
•
»
:
),
7
Ú
:
L
«
ž
“
o
:
.
Ï
•
²
¡
4
·
8
2
‚
f
ã
ä
k
é
¡
5
,
¤
±
ž
“
o
:
/
¤
•
Œ
ž
,
Œ
±
u
y
3
½:
DOI:10.12677/aam.2021.10114314059
A^
ê
Æ
?
Ð
0
ƒ
•
êž
k
:
ä
k
ƒ
Ó
•
¹
ê
¿
…
k
a
q
o
ü
Ñ
.
~
X
,
:
v
i
2
,
v
i
+1
2
,
···
,
v
i
+
j
2
Ñ
3
Ó
˜
,
¿
…
§
‚
•
¹
ê
•
g
•
sn
(
v
i
2
),
sn
(
v
i
+1
2
),
···
,
sn
(
v
i
+
j
2
),
@
o
Œ
±
ª
sn
(
v
i
2
)=
sn
(
v
i
+1
2
)
=
···
=
sn
(
v
i
+
j
2
).
Š
â
²
¡
4
·
8
2
‚
f
ã
Ê
b
•
ª
Ú
E
,
Œ
±
½
Â
n
«
Ø
Ó
:
8
,
¿
…
±
e
y
²
L
§
Ñ
¦
^
ù
«
:
8
©
a
.
V
2
1
=
{
v
∈
V
2
|
v
˜
‡
Ý:
Ú
˜
‡
n
Ý:
,
½
ö
Ñ
´
Ý:
}
.
V
3
1
=
{
v
∈
V
3
|
v
Ý:
Ú
n
Ý:
}
.
V
3
2
=
{
v
∈
V
3
|
v
Ñ
´
n
Ý:
}
,
ù
p
V
2
L
«
3
G
t
(
n,m
)
¥
Ý
ê
•
2
:
8
,
V
3
ä
k
a
q
½
Â
:
8
.
Ä
k
y
²
G
t
(
n,
3)
•
¹
Ç
¿
…
3
G
t
(
n,
3)
¥
•[
Q
ã
ù
‡
o
L
§
.
½
n
2.2
é
u
G
t
(
n,
3),
K
ρ
(
G
t
(
n,
3)) =
324
n
2
+784
n
+684
(18
n
+26)
2
.
y
²
-
1
1
:
ê
•
n
,
K
k
1
4,7,10
:
ê
•
n
2
+1,
Ù
{
:
ê
Ñ
†
1
1
ƒ
Ó
,
V
(
G
t
(
n,
3)) = 18
n
+26(
n
≥
3).
œ
/
1
e
»
:
´
V
1
2
¥
:
.
X
J
v
1
1
∈
V
1
2
´
»
:
.
3
ž
•
t
=1
o
v
2
1
;
t
=2
o
v
1
3
,
d
ž
»
Ò
Ø
2
ø
ò
.
d
d
Œ
±
sn
(
v
1
1
) = 18
n
+24.
†
v
1
1
k
a
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
1
2
,
v
n
2
+1
2
,
v
1
3
,
v
n
2
+1
3
,
v
1
5
,
v
n
2
+1
5
,
v
1
6
,
v
n
2
+1
6
,
v
1
8
,
v
n
2
+1
8
,
v
1
9
,
v
n
2
+1
9
,
v
1
11
,
v
n
2
+1
11
,
v
1
12
,
v
n
2
+1
12
;
v
2
1
,
···
,
v
n
1
;
v
1
13
,
···
,
v
n
13
.
œ
/
2
e
»
:
´
V
1
3
¥
:
.
X
J
v
2
2
∈
V
1
3
´
»
:
.
3
ž
•
t
= 1
o
v
2
3
;
t
= 2
o
v
4
1
;
t
=3
o
v
1
2
,
d
ž
»
Ø
2
ø
ò
.
d
d
Œ
±
sn
(
v
2
2
)=18
n
+22.
†
:
v
2
2
k
a
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
3
2
,
v
4
2
,
···
,
v
n
2
2
;
v
2
12
,
v
3
12
,
···
,
v
n
2
12
;
v
1
7
,
v
n
7
.
œ
/
3
e
»
:
´
V
2
3
¥
:
.
f
œ
/
3.1
X
J
v
2
3
∈
V
2
3
´
»
:
.
3
ž
•
t
=1
o
v
2
2
m
©
ï
á
˜
‡
Ü
Ü
“
»
p
;
t
=2
o
v
4
4
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
;
t
=3
o
v
2
6
m
©
ï
á
˜
‡
H
Ü
Y
²
•
•
“
»
p
;
t
=4
o
v
1
6
¦
·
ò
•
H
Ü
“
»
p
•
Ý
¿
…
†
‚
f
ã
À
Ü>
.
-
Ü
;
t
= 5
o
v
1
1
m
©
ï
á
˜
‡
Ü
“
»
p
¿
…
†
‚
f
ã
À
Ü>
.
-
Ü
.
–
d
ù
Ø
Ó
•
•
“
»
p
Ú
‚
f
ã
>
.
*
d
Ñ
p
ƒ
-
Ü
•
ª
/
¤
•
Œ
¦
»
Ê
Ž
ø
ò
,
v
2
3
•
¹
ê
L
ˆ
ª
sn
(
v
2
3
) = 18
n
+18.
†
:
v
2
3
k
a
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
n
2
3
;
v
2
4
,
v
3
4
,
···
,
v
n
−
1
4
;
v
2
11
,
v
n
2
11
;
v
2
10
,
v
3
10
,
···
,
v
n
−
1
10
;
v
2
5
,
v
n
2
5
,
v
2
6
,
v
n
2
6
,
v
2
7
,
v
n
−
1
7
,
v
2
8
,
v
n
2
8
,
v
2
9
,
v
n
2
9
.
f
œ
/
3.2
X
J
v
3
3
∈
V
2
3
´
»
:
.
3
ž
•
t
=1
o
v
4
4
m
©
ï
á
˜
‡
Ü
Ü
“
»
p
;
t
=2
o
v
6
4
m
©
ï
á
˜
‡
À
Ü
“
»
p
;
t
=3
o
v
3
6
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
¿
…
†
À
Ü
“
»
p
-
Ü
;
t
=4
o
v
2
2
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
¿
…
†
‚
f
ã
Ü>
.
-
Ü
;
t
= 5
o
:
v
4
3
¦
·
ò
•
À
Ü
“
»
p
•
Ý
;
t
=6
o
v
8
1
¦
À
Ü
“
»
p
†
‚
f
ã
Ü>
.
-
Ü
.
•
ù
“
»
p
†
‚
f
ã
>
.
*
d
-
Ü
¿
…
/
¤
•
Œ
,
v
3
3
•
¹
ê
L
ˆ
ª
sn
(
v
3
3
) = 18
n
+16.
†
:
v
3
3
k
a
DOI:10.12677/aam.2021.10114314060
A^
ê
Æ
?
Ð
0
ƒ
•
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
4
3
,
v
5
3
,
···
,
v
n
2
−
1
3
;
v
3
11
,
v
4
11
,
···
,
v
n
2
−
1
11
.
f
œ
/
3.3
X
J
v
3
5
∈
V
2
3
´
»
:
.
3
ž
•
t
=1
o
v
3
6
m
©
ï
á
˜
‡
H
Ü
“
»
p
;
t
=2
o
v
6
4
m
©
ï
á
˜
‡
À
Ü
“
»
p
;
t
=3
o
v
2
5
m
©
ï
á
˜
‡
Ü
Ü
“
»
p
;
t
=4
o
v
2
4
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
;
t
= 5
o
v
6
1
¦
·
ò
•
À
Ü
“
»
p
•
Ý
¿
…
†
‚
f
ã
Ü>
.
-
Ü
;
t
=6
o
v
1
1
¦
Ü
Ü
“
»
p
†
‚
f
ã
Ü>
.
ƒ
-
Ü
.
•
ù
“
»
p
†
‚
f
ã
>
.
*
d
-
Ü
/
¤
˜
‡
•
Œ
¿
…
{
Ž
»
ø
ò
,
v
3
5
•
¹
ê
L
ˆ
ª
sn
(
v
3
5
) = 18
n
+14.
†
:
v
3
5
k
a
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
4
5
,
v
5
5
,
···
,
v
n
2
−
1
5
;
v
3
9
,
v
4
9
,
···
,
v
n
2
−
1
9
;
v
3
7
,
v
n
−
2
7
.
f
œ
/
3.4
X
J
v
3
6
∈
V
2
3
´
»
:
.
3
ž
•
t
=1
o
v
3
5
m
©
ï
á
˜
‡
Ü
“
»
p
;
t
=2
o
v
3
7
m
©
ï
á
˜
‡
Ü
Ü
“
»
p
;
t
= 3
o
v
3
9
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
;
t
= 4
o
v
4
5
m
©
ï
á
˜
‡
À
Ü
“
»
p
;
t
=5
o
v
8
7
¦
·
ò
•
À
Ü
“
»
p
•
Ý
;
t
=6
o
v
8
10
?
·
ò
•
À
Ü
“
»
p
•
Ý
;
t
=7
o
v
4
12
m
©
ï
á
˜
‡
H
Ü
“
»
p
¿
…
†
Ü
Ü
“
»
p
-
Ü
;
t
= 8
o
v
3
12
¦
·
ò
•
H
Ü
“
»
p
•
Ý
;
t
=9
o
v
3
10
¦
·
ò
•
Ü
Ü
“
»
p
•
Ý
¿
…
†
H
Ü
“
»
p
-
Ü
.
•
ù
“
»
p
†
‚
f
ã
>
.
*
d
-
Ü
/
¤
˜
‡
•
Œ
¿
…
{
Ž
»
ø
ò
.
v
3
6
•
¹
ê
L
ˆ
ª
sn
(
v
3
6
)=18
n
+11.
†
:
v
3
6
k
a
q
o
ü
Ñ
Ú
ƒ
Ó
•
¹
ê
:
k
:
v
4
6
,
v
5
6
,
···
,
v
n
2
−
1
6
;
v
4
7
,
v
5
7
,
···
,
v
n
−
3
7
;
v
3
8
,
v
4
8
,
···
,
v
n
2
−
1
8
.
Figure2.
Thegraphofsubcase3.4
ã
2.
f
œ
/
3.4
«
¿
ã
n
Ü
þ
ã
í
n
L
§
,
Œ
±
•
¹
ê
•
sn
(
v
) = 18
n
+24,
sn
(
v
) = 18
n
+22,
sn
(
v
) = 18
n
+18,
sn
(
v
)=18
n
+ 16,
sn
(
v
)=18
n
+ 14,
sn
(
v
)=18
n
+ 11
:é
A
‡
ê
L
ˆ
ª
•
g
•
4
n
+ 20,
2
n
+6,4
n
+14,2
n
−
4,2
n
−
2,4
n
−
8.
r
ù
‡
ê
?
1
¦
Ú
,
•
Œ
±
G
t
(
n,
3)
•
¹
Ç
.
O
Ž
L
§
L
ˆ
ª
X
e
:
sn
(
G
t
(
n,
3)) = (4
n
+20)(18
n
+24)+(2
n
+6)(18
n
+22)
+(4
n
+14)(18
n
+18)+(2
n
−
4)(18
n
+16)
+(2
n
−
2)(18
n
+14)+(4
n
−
8)(18
n
+11)
= 324
n
2
+784
n
+684
DOI:10.12677/aam.2021.10114314061
A^
ê
Æ
?
Ð
0
ƒ
•
¤
±
,
ρ
(
G
t
(
n,
3)) =
324
n
2
+784
n
+684
(18
n
+26)
2
(
n
≥
3).
é
u
m
=1
!
2,
Œ
±
Š
â
þ
ã
m
= 3
œ
¹
?
1
a
q
í
n
y
²
L
§
X
e
(
J
.
½
n
2.3
é
u
G
t
(
n,
1),
K
ρ
(
G
t
(
n,
1)) =
100
n
2
+228
n
+172
(10
n
+14)
2
.
y
²
3
G
t
(
n,
1)
‚
f
ã
¥
:
‡
ê
V
(
G
t
(
n,
1))=10
n
+14.
¿
…
Œ
±
•
¹
ê
•
sn
(
v
)=
10
n
+ 12,
sn
(
v
)=10
n
+ 10,
sn
(
v
)=10
n
+ 6,
sn
(
v
)=10
n
+4
:é
A
‡
ê
Ï
‘
L
ˆ
ª
•
g
•
4
n
+12,2
n
+2,2
n
+4,2
n
−
4.
•
ã
G
t
(
n,
1)
•
¹
ê
X
e
O
Ž
L
ˆ
ª
:
sn
(
G
t
(
n,
1)) = (4
n
+12)(10
n
+12)+(2
n
+2)(10
n
+10)
+(2
n
+4)(10
n
+6)+(2
n
−
4)(10
n
+4)
= 100
n
2
+228
n
+172
¤
±
,
ρ
(
G
t
(
n,
1)) =
100
n
2
+228
n
+172
(10
n
+14)
2
(
n
≥
2).
½
n
2.4
é
u
G
t
(
n,
2),
K
ρ
(
G
t
(
n,
2)) =
196
n
2
+468
n
+316
(14
n
+20)
2
.
y
²
3
G
t
(
n,
2)
‚
f
ã
:
‡
ê
V
(
G
t
(
n,
2)) = 14
n
+20.
Œ
±
•
¹
ê
•
sn
(
v
) = 14
n
+18,
sn
(
v
) = 14+16,
sn
(
v
) = 14
n
+12,
sn
(
v
) = 14
n
+10,
sn
(
v
) = 14
n
+8
:é
A
‡
ê
Ï
‘
L
ˆ
ª
•
g
•
4
n
+16,2
n
+4,4
n
+8,2
n
−
4,2
n
−
4.
•
Œ
±
ã
G
t
(
n,
2)
•
¹
ê
X
e
O
Ž
í
n
L
§
:
sn
(
G
t
(
n,
2)) = (4
n
+16)(14
n
+18)+(2
n
+4)(14
n
+16)
+(4
n
+8)(14
n
+12)+(2
n
−
4)(14
n
+10)
+(2
n
−
4)(14
n
+8) = 196
n
2
+468
n
+316
¤
±
,
ρ
(
G
t
(
n,
2)) =
196
n
2
+468
n
+316
(14
n
+20)
2
(
n
≥
3).
m
=4
ž
,
Œ
±
G
t
(
n,
4)
º:
ê
V
(
G
t
(
n,
4))=22
n
+32,
¿
…
ã
¥
¤
k
:é
A
•
¹
ê
«
a
ê
†
þ
ã
m
= 3
œ
¹
ƒ
Ó
.
Ï
L
o
(
Ú
í
2
,
é
u
?
¿
k
•
m
Ú
n
,
Œ
±
ã
G
t
(
n,m
)
º:
ê
Ú
m
,
n
ƒ
m
'
X
L
ˆ
ª
V
(
G
t
(
n,m
)) = 4(
m
+1)(
n
+1)+2(
m
+
n
+2),
ù
p
m,n
∈
N
+
.
¿
…
Œ
±
3
‚
f
ã
G
t
(
n,m
)
¥
:(1)
•
¹
ê
•
sn
(
v
)=(
V
(
G
t
(
n,m
))
−
2)
:
ê
4(
n
+
m
+ 2);
(2)
•
¹
ê
•
sn
(
v
)=(
V
(
G
t
(
n,m
))
−
4)
:
ê
2(
m
+
n
);(3)
•
¹
ê
•
sn
(
v
)=(
V
(
G
t
(
n,m
))
−
8)
:
ê
4
n
+6
m
−
4;(4)
•
¹
ê
•
sn
(
v
) = (
V
(
G
t
(
n,m
))
−
10)
:
ê
2
n
−
4;(5)
•
¹
ê
•
sn
(
v
) =
(
V
(
G
t
(
n,m
))
−
12)
:
ê
2(
m
+
n
)
−
8;(6)
•
¹
ê
•
sn
(
v
) = (
V
(
G
t
(
n,m
))
−
15)
:
3
ã
¥
ä
k
X
e
˜
A
:
ù
:
u
˜
‡
Ý
/
«
•
¥
,
ù
‡
Ý
/
«
•
>
.
þ
:
Ú
«
•
p
¡
:Ñ
´
Î
Ü
:
,
…
ù
‡
Ý
/
«
•
>
.
þ
:
‚
f
ã
>
.
þ
Ý
ê
•
2
:
å
l
Ñ
´
5.
ù
p
å
l
´
•
ü
:
ƒ
m
•
á
´
•
Ý
.
2.2.
Ã
•
²
¡
4
·
8
2
‚
f
Ã
•
ã
ž
“
¯
K
Ì
‡
ï
Ä
3
‰
½
ž
“
ê
8
c
J
e
´
Ä
U
3
k
•
ž
m
S
ò
»
›
›
4
,
½
ö
ž
“
X
Û
“
o
¦
•
¼
Í
º:
ê
•
õ
.
é
u
Ã
•
²
¡
4
·
8
2
‚
f
ã
,
'
5
-
:
´
X
J
z
‡
£
Ü
•
¦
^
˜
‡
ž
“
@
o
é
u
?
¿˜
‡
»
:
´
Ä
Œ
±
›
›
»
ø
ò
.
Š
â
Ú
n
2.1
o
g
Ž
U
Ä
Œ
±
é
˜
‡
'
Ð
o
ü
Ñ
¦
ž
“
/
¤
˜
‡
•
Œ
.
e
¡
½
n
2.6
y
²
ù
‡
ß
Ž
¿
…
‰
Ñ
›
›
»
‡
L
§
¦
^
£
Ü
ê
Ú
-
:
‡
ê
e
.
.
-
v
j
i
L
«
²
¡
4
·
8
2
‚
f
ã
¥
?
¿˜
:
,
:
v
j
i
‹
I
9
Ù
:
I
P
•
ª
X
ã
3
¤
«
.
DOI:10.12677/aam.2021.10114314062
A^
ê
Æ
?
Ð
0
ƒ
•
Figure3.
Thecoordinateof
v
j
i
anditsneighbourhood
ã
3.
v
j
i
:
‹
I
9
Ù
:
«
¿
ã
½
n
2.5
é
u
Ã
•
²
¡
4
·
8
2
‚
f
ã
X
J
z
‡
£
Ü
¦
^
˜
‡
ž
“
,
@
o
3
1
9
‡
£
Ü
(
å
ù
‡
»
Ò
Ø
2
ø
ò
,
…
-
:
‡
ê
•
•
15.
y
²
3
Ã
•
²
¡
4
·
8
2
‚
f
ã
¥
,
•
k
n
Ý:
•
3
ã
¥
.
¦
^
o
ü
Ñ
X
e
:
3
ž
m
t
= 0,
b
²
¡
4
·
8
2
‚
f
ã
¥
?
˜
:
v
j
i
•
»
:
;
t
= 1
˜
˜
ž
“
3
v
j
+1
i
;
t
= 2
ž
“
˜
3
v
j
−
1
i
−
2
;
t
= 3
ž
“
˜
3
v
j
−
3
i
¿
…
·
ò
•
“
»
p
•
Ý
;
t
=4
ž
“
˜
3
v
j
+1
i
+3
{
Ž
»
ø
ò
;
t
=5
˜
˜
ž
“
3
v
j
−
1
i
+5
m
©
ï
á
˜
‡
À
Ü
“
»
p
;
t
= 6
˜
˜
ž
“
3
v
j
−
4
i
+5
·
ò
•
À
Ü
“
»
p
•
Ý
;
t
= 7
˜
˜
ž
“
3
v
j
−
6
i
+3
¿
…
m
©
ï
˜
‡
H
Ü
“
»
p
;
t
= 8
˜
˜
ž
“
3
v
j
−
6
i
·
ò
•
H
Ü
“
»
p
•
Ý
;
t
=9
˜
˜
ž
“
3
v
j
−
4
i
−
2
·
ò
•
Ü
Ü
“
»
p
•
Ý
¿
…
†
H
Ü
“
»
p
ƒ
-
Ü
.
•
ª
ù
“
»
p
*
d
ƒ
-
Ü
/
¤
˜
‡
•
Œ
¦
»
Ø
2
D
Â
.
X
ã
2
¤
«
,
˜
˜
ž
“
3ù
:
˜
þ
Œ
±
:
•
¹
ê
•
sn
(
v
) =
V
(
G
t
(
n,m
))
−
15.
l
Ã
•
²
¡
4
·
8
2
‚
f
ã
(
,
Œ
±
w
Ñ
du
l
>
/
Ê
b
•
ª
)
˜
•
/
,
ù
•
/
þ
X
»
:
3
k
•
g
o£
Ü
¦
£
c
¡
®
²
-
:
C
˜
,
Ï
d
Œ
±
~
-
:
CX
«
•
.
¤
±
F
"
˜
˜
ž
“
Œ
±
¦
Œ
U
£
»
:
C
˜
þ
,
?
/
¤
˜
‡
•
Œ
¦
»
Ø
2
ø
ò
.
»
Ê
Ž
ø
ò
ž
,
þ
ã¦
^
o
ü
Ñ
¦
-
«
•
•
•
¹
9
‡
l
>
/
,
„
Œ
±
w
ù
‡
-
«
•
•
¡
˜
ž
“
‡
ê
•
9,
¿
…
ù
‡
-
«
•
o
-
:
‡
ê
•
•
15,
X
ã
2
¤
«
.
Ä
7
‘
8
I
[
g
,
‰
Æ
Ä
7
‘
8
(11761070,61662079);2021
c
#
õ
‘Æ
g
£
«
g
,
Ä
7
é
Ü
‘
8
(2021D01C078);2020
c
#
õ
“
‰
Œ
Æ
˜
6
;
’
!
˜
6
‘
§
‘
8
]
Ï
.
ë
•
©
z
[1]Hartnell,B.L.(1995)Firefighter!AnApplicationofDomination.
Presentationatthe25th
ManitobaConferenceonCombinatorialMathematicsandComputing
, University ofManitoba,
Winnipeg,Canada.
DOI:10.12677/aam.2021.10114314063
A^
ê
Æ
?
Ð
0
ƒ
•
[2]Cai,L.Z.andWang,W.F. (2009)TheSurvivingRateofaGraphfor theFirefighterProblem.
DiscreteMathematics
,
23
,1814-1826.https://doi.org/10.1137/070700395
[3]Ng,K.L.andRaff,P.(2008)AGeneralizationoftheFirefighterProblemonZ
×
Z.
Discrete
AppliedMathematicsandCombinatorialComputing
,
156
,730-745.
[4]Wang,W.,Finbow,S.andWang,P.(2010)OntheSurvivingRateofaGraph.
Theoretical
ComputerScience
,
411
,3651-3660.https://doi.org/10.1016/j.tcs.2010.06.009
[5]Adjiashvili,D.,Baggio,A.andZenklusen,R.(2017)FirefightingonTreesbeyondIntegrality
Graphs.
ProceedingsoftheTwenty-EighthAnnualACM-SIAMSymposiumonDiscreteAlgo-
rithms(SODA2017)
,Barcelona,16-19January2017,2364-2383.
https://doi.org/10.1137/1.9781611974782.156
[6]Shorck,R.andWu,F.Y.(2000)SpanningTreesonGraphsandLatticesin
d
Dimensions.
JournalofPhysicsA:MathematicalandGeneral
,
33
,3881-3902.
https://doi.org/10.1088/0305-4470/33/21/303
DOI:10.12677/aam.2021.10114314064
A^
ê
Æ
?
Ð