小直径单圈图的永久和指标的极值研究 Extremal Unicyclic Graphs of the Small Diameter with Respect to Permanental Sum

doi:10.12677/PM.2021.1111216

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

PureMathematicsnØêÆ,2021,11(11),1933-1948

PublishedOnlineNovemb er2021inHans.http://www.hanspub.org/journal/pm

https://doi.org/10.12677/pm.2021.1111216

†»üã[ÈÚ•I4ŠïÄ

xxx===fff

“°¬xŒÆêÆ†ÚOÆ§“°Üw

ÂvFÏµ2021c1019F¶¹^FÏµ2021c1123F¶uÙFÏµ2021c1130F

Á‡

-GL«˜‡n‡º:ã"ã[ÈÚ´•ãÈÚõ‘ªX êýéŠƒÚ"ã[ÈÚ

OŽy²´]p-"©¥§• x†»•3Ú4üã[È Ú.§¿‰ÑˆT

.4ã"

'…c

ÈÚõ‘ª§[ÈÚ§Hosoya•I§üã

ExtremalUnicyclicGraphsofthe

SmallDiameterwithRespectto

PermanentalSum

YinggangBai

SchoolofMathematicsandStatistics,QinghaiNationalitiesUniversity,XiningQinghai

Received:Oct.19

,2021;accepted:Nov.23

,2021;published:Nov.30

,2021

Abstract

Let Gbeagraphwith nvertex,thepermanentalsumof Gisthesumoftheabsolute

©ÙÚ^:x=f.†»üã[ÈÚ•I4ŠïÄ[J].nØêÆ,2021,11(11):1933-1948.

DOI:10.12677/pm.2021.1111216

x=f

valutesofthecoﬃcients.Computingthepermanentalpolynomialsofgraphsis]p.

Inthispaper,wewilldeterminethegraphminimizingthepermanentalsumamong

allunicyclicgraphswithdiameter 3and4,andthecorrespondingextremalbicyclic

graphsarealsodetermined.

Keywords

PermanentalPolynomial,PermanentalSum,HosoyaIndex,

UnicyclicGraph

2021byauthor(s)andHansPublishersInc.

This work is licensed undertheCreative Commons Attribution International License (CCBY 4.0).

http://creativecommons.org/licenses/by/4.0/

1.0

n•M= (m

)ÈÚª½ÂXe:

per(M) =

i=1

iσ( i)

ùpÚªH{1,2,...,n}¥¤k˜†σ"-A(G)•ãGÝ,õ‘ªπ(G,x)=

per(xI−A(G))=

k=0

(G)x

n−k

•ãGÈÚõ‘ª, Ù¥I•ü Ý"b

(G) L«ãG

ÈÚõ‘ªXê"Merris[1]‰Ñe¡OŽÈÚõ‘ªXêSachsúª,

(G) = (−1)

H∈S

(G)

C(H)

(0 ≤k≤n)

ùpÚHãGk‡º:Sachsfã,S

(G)´ãG¥k‡º:Sachsfã"~X

(G)=0 , Ï•S

(G) ´˜8; b

(G)=n, Ï•S

(G)=|E(G)|"PS(G) ½Â•ãG[ÈÚ,

=Π(G,x) z˜‘XêýéŠƒÚ,K

PS(G) =

k=0

(G)|=

k=0

H∈S

(G)

C(H)

·‚½µ˜ã[ÈÚ•1"

DOI:10.12677/pm.2021.11112161934nØêÆ

x=f

dKasum [2] <ïÄzÆ©z¥ã/ÈÚõ‘ª, ¦‚©OOŽ´»ÚÈÚõ‘

ª±9ùõ‘ª":"Cash [3]ïÄzÆã(•),`,)L,C

LVL)ÈÚõ‘

ª"¦•ÑïÄÈÚõ‘ª´k¿Â "´, ãÈÚõ‘ªXêOŽ´]p"†

y3•kê'uzÆãÈÚõ‘ªXê±9§d3A^Ñ‡[4]-[14]"@oXÛïÄz

ÆãÈÚõ‘ªXê=XÛ•xzÆã[ÈÚ"[ÈÚ† zÆy–ƒmkX;—éX"é

g,.ïÄL², C

¥•3271‡šÓLV L"8c•Ž, 3C

¥•kêLVLé

"2004cXie[15]<˜‡Ø-½LVLC

)"Tong<[16] OŽC

¥271

‡LVL[ÈÚ, ¦‚uyC

[ÈÚ33271‡LVL¥ˆ•Š"¦‚„•Ñ[ÈÚ†

©fã-½5—ƒƒ'"[ÈÚOŽ´]p[17]"¦+Xd,Cc5é[ÈÚïÄÚå

ïÄö2•'5"Chou <[18]ïÄC

5Ÿ"o<[19]•x8•ó[ÈÚ"Li

ÚWei[20] <•xAló[ÈÚ"Wu ÚLai[21] ïÄ˜„ã[ÈÚÄ5Ÿ,

¦‚•Ñ[ ÈÚ†ÜÅ@êêk'X,'uÈÚªµ±9k'(Øž[22]-[25]"d

, [ÈÚ†Hosoya•êk'X"ãGHosoya•ê^Z(G) L«, ½Â•ãGÕá>8

oê[26]"Hosoya•ê†zÆã£:—ƒƒ'"WuÚLai[21]ïÄL²PS(G) ≥Z(G),3ã

G´äœ¹eÒ¤á"ùL²[ÈÚéŒU)ºzÆ©f,A"

©z[27] •xn†»Ø‡L4 üãHarary•ê•Š"3dÄ:þ, ©•x

n†»•3 üã[27] Ú†»•4[27]üã[ÈÚ.,9ˆU.4ã"

2.ÄVg

-G=(V(G),E(G)) L«˜‡ã, ãGº:8P•V(G) , >8P•E(G) , º:8Œ¡

•ãG, Ù¥•0 ã¡•˜ã"N

(v) L«†º:vƒº:¤8Ü, n‡º:

(,´,©OL«•S

"eW⊆V(G),·‚^G−WL«lãG¥íK8ÜW¥

Üº:±9†ù:ƒ'é>Gfã"aq, eE

⊆E(G) ,^G−E

L«lãG¥í

K8ÜE

¥>Gfã"Sachsfã•dØ½á>|¤ã"v∈V(G) , G¥†

:v'é>^ê¡•vÝ, P•d

(v) ½öd(v)"·‚rÝ•1 :¡•]!:, Ý•0

:¡•á:"D´Ã•ã, x,y∈V(D)"lXyål´•D¥•á(x,y) ´•, P•

(x,y)"eãD ¥Ø•3(x,y) ´,K½d

(x,y)= +∞"˜„/, d

(x,y)6= +∞"ãD†

»P•d(D),½Â•: d(D) = max{d

(x,y) : ∀x,y∈V∈(D)}"

3.Ún

½Â3.1[28]u´ãG

˜‡º:,ãG

(„ã1)L«rãG

˜‡º:uÚäT

˜

‡º:v^˜^>ƒëã, ãG

(„ã1) L«rº:uÚ(S

¥%v^˜^>ƒë

ã,,rlãG

C†ãG

¡•C†˜"

Ún3.2[28] ãG

ÚãG

X½Â2.1¤½Â,KPS(G

)≥PS(G

),Ò¤á…=

T´˜‡(¿…u´T¥%"

½Â3.3[28]ãG

(„ã1)X½Â2.1¤½Â, ^G

(„ã1)L«r(S

n+1

¥%v Ú

º:uÅ3˜åã, rãG

C†ãG

¡•C†"

DOI:10.12677/pm.2021.11112161935nØêÆ

x=f

Figure1.G

ã1.G

Ún3.4[28]ãG

X½Â2.1 ¤½Â,ãG

X½Â2.3 ¤½Â,KPS(G

) ≥PS(G

),Ò

¤á…=T= K

½öu´G

á:"

½Â3.5[28]G

´˜‡üã…C

= u

···u

´•˜,u

Úu

´ü‡Ý•

2 º:,1≤i≤j≤r"^G

(„ã2)L«©Ors≥1 Út≥1 ‡]!:ëãü‡º

Úu

ã;^G

(„ã2)L«rs+t‡]!:ëG

º:u

ã;G

(„ã2)L«r

s+ t‡]!:ëG

º:u

ã, rlãG

C†ãG

, ½lãG

C†ãG

¡•C

†n"

Figure2.G

ã2.G

Ún3.6[28]ãG

X½Â2.5¤½Â,KPS(G

)>PS(G

)½öPS(G

PS(G

Ún3.7[28]n≥5, 4 ≤r≤n−1 ,G(r,n−r) („ã3)L«C

,˜‡º:†S

n−r+1

¥

%ƒÊnüã, PS(G(r,n−r)) >PS(G(r−1,n−r+1))"

Figure3.G(r,n−r),G(r−1,n−r+1)

ã3.G(r,n−r),G(r−1,n−r+1)

Ún3.8[28]ã[ÈÚ÷vXe5Ÿ:

DOI:10.12677/pm.2021.11112161936nØêÆ

x=f

(1)ãG ÚãH •ëÏã, V(G) †V(H) ©OL«ãGÚãHº:8, V(G)

V(H)= φ,

KPS(G

H) = PS(G)PS(H)"

(2)e= uv∈E(G) ,K

PS(G) = PS(G−e)+PS(G−u−v)+2

C∈C

(e)

PS(G−V(C))

(3)v∈V(G) ,K

PS(G) = PS(G−v)+

u∈N

(v)

PS(G−u−v)+2

C∈C

(v)

PS(G−V(C))

(v) L«G¥v:8Ü, C

(e)L«G¥•¹>e8Ü, C

(v) L«G¥•¹º

:v8Ü"

4.†»•3üã(„ã4)[ÈÚ4ŠïÄ

Figure4.SinglecirclediagramG

(a,b),G

(a,b,c),G

(a,b),G

(a,b)withdiameter3

ã4.†»•3üãG

(a,b),G

(a,b,c),G

(a,b),G

(a,b)

ãG

(a,b),G

(a,b,c),G

(a,b),G

(a,b) ¥a,b,cI‡÷v±e^‡:

(a,b) ¥,a, bþŒuu0,a+b+5 = n"

(a,b,c)¥a,b,c–ü‡êŒuu1 ,a+b+c+3 = n""

(a,b) ¥a, b–˜‡êŒuu1,a+b+4 = n"

(a,b) ¥a, b–˜‡êŒuu1,a+b+5 = n"

±þa,b, cþ•g,ê, n≥7"

½n4.1-G

(n) = {G

(a,b),G

(a,b,c),G

(a,b),G

(a,b)}L«†»•3nüã8

Ü,G∈G

(n),KPS(G) ≥3n−4, …=G

∼

(a+b+c−1,0,1)(„ã5)žÒ¤á"

y²

(I)éG

(a,b,c) A^C†n, C•G

(a+b,0,c) , =r†º:v

ƒë¤k]!:íØÚ

DOI:10.12677/pm.2021.11112161937nØêÆ

x=f

º:v

ƒë,dÚn3.6 

PS(G

(a,b,c) ≥PS(G

(a+b,0,c))(1)

Figure5.G

(a+b+c−1,0,1),G

(1,m+t−1))

ã5.G

(a+b+c−1,0,1),G

(1,m+t−1))

-a+b=s,c=t,s+t+ 3=n,PS(G

(a+b,0,c))=PS(G

(s,0,t)) (s≥1,t≥1), dÚn

3.8

PS(G

(s,0,t)) = 2s+2t+st+6,PS(G

(s+1,0,t−1)) = 2(s+1)+2(t−1)+(s+1)(t−1)+6"

KPS(G

(s,0,t))−PS(G

(s+1,0,t−1)) = PS(G

(a+b,0,c))−PS(G

(a+b+1,0,c−1)) =

s−t+1,©ü«œ¹"

œ¹˜s−t+1 ≥0ž, PS(G

(s,0,t)) ≥PS(G

(s+1,0,t−1))"

PS(G

(s+t−1,0,1)) ≤PS(G

(s+t−2,0,2)) ≤···≤PS(G

(s,0,t))"

¤±PS(G

(a+b,0,c)) = PS(C

(s,0,t)) ≥PS(C

(s+t−1,0,1)) = 3n−4"

œ¹s−t+1 <0ž, PS(G

(s,0,t)) <PS(G

(s+1,0,t−1))"

PS(G

(1,0,s+t−1)) <PS(G

(2,0,s+t−2)) <···<PS(G

(s,0,t))"

PS(G

(a+b,0,c)) = PS(G

(s,0,t)) ≥PS(G

(1,0,s+t−1)) = 3n−4"

:

PS(G

(a+b,0,c)) ≥3n−4(2)

d(1)(2) G

∼

(a,b,c),PS(G) ≥3n−4,G

∼

(a+b+c−1,0,1)Ò¤á"

(II)éG

(a,b) A^C†nC¤G

(a+b,0), =r†º:v

ƒë]!:ÜíØÚº:v

ë,dÚn3.6 PS(G

(a,b)) ≥PS(G

(a+b,0))"

dÚn3.8PS(G

(a+b,0)) = 3n−3"

¤±

PS(G

(a,b)) ≥3n−3(3)

(III)éG

(a,b) A^C†n, C¤G

(a+ b,0) =r†º:v

ƒë]!:íØÚº:v

,dÚn3.6 PS(G

(a,b)) ≥G

(a+b,0)

DOI:10.12677/pm.2021.11112161938nØêÆ

x=f

dÚn3.8PS(G

(a+b,0)) = 5n−12"

¤±

PS(G

(a,b)) ≥5n−12(4)

(IV)dÚn3.8PS(G

(a,b)) = 2(a+3)(b+2)+2"

PS(G

(a+1,b−1)) = 2(a+4)(b+1)+2,PS(G

(a,b))−PS(G

(a+1,b−1)) = a−b+2"

©ü«œ¹"

œ¹˜a−b+2 ≥0ž, PS(G

(a,b)) ≥G

(a+1,b−1)), :

PS(G

(a+b,0)) ≤PS(G

(a+b−1,1) ≤···≤PS(G

(a,b))"

¤±PS(G

(a,b)) ≥PS(G

(a+b,0)) = 4n−6"

œ¹a−b+2 <0ž, PS(G

(a,b)) <G

(a+1,b−1)),, :

PS(G

(0,a+b)) ≤PS(G

(1,a+b−1)) ≤···≤PS(G

(a,b))"

¤±PS(G

(a,b)) ≥PS(G

(0,a+b)) = 6n−18"

du6n−18 >4n−6, ¤±

(a,b)) ≥4n−6(5)

G

∼

(a+b+c−1,0,1)ž,d(.) PS(G) = 3n−4"

G6= G

(a+b+c−1,0,1)ž,©o«œ¹"

œ¹˜G

∼

(a,b,c)ž,d(2)PS(G) >3n−4"

œ¹G

∼

(a,b) ž,d(3) PS(G) ≥3n−3 >3n−4"

œ¹nG

∼

(a,b) ž,d(4) PS(G) ≥5n−12 >3n−4"

œ¹oG

∼

(a,b) ž,d(5) PS(G) ≥4n−6 >3n−4"

¤±G∈G

(n)(n≥7),KPS(G) ≥3n−4,…=G

∼

(a+b+c−1,0,1) žÒ

¤á"

5.†»•4üã(„ã6)[ÈÚ4ŠïÄ

ãG

¥ëêI‡÷v±e^‡:

¥,a

þŒuu1,i∈{1,2,...,k}"

¥©ü«œ¹:(1)p

–˜‡êŒuu1, a

þŒu1"i∈{1,2,...,k}"

(2)p

= p

= 0,a

–kü‡êŒuu1, i∈{1,2,...,k}"

(3)G

¥p

= p

= 0,a

–k˜‡êŒuu1,i∈{1,2,...,k}"

DOI:10.12677/pm.2021.11112161939nØêÆ

x=f

Figure6.Diagramofasinglecirclewithadiameterof4

ã6.†»•4üã

(4)G

¥÷vp

6= 0½öp

6= 0"

(5)G

¥,p

= p

= 0,a

–k˜‡êŒuu1,i∈{1,2,...,k}"

(6)G

¥,p

6= 0,p

6= 0Úp

6= 0±þœ¹–˜«œ¹¤á"

(7)G

–k˜‡p

Œuu1, i∈{1,2,3}"

±þs, r, a

,i∈{1,2,...,k}þ•g,ê, n≥8"

Ún5.1PS(G

(s,r,a

,...,a

)) ≥6n−14"

y²

(I)k≥2 ž"

éãG

(s,r,a

,...,a

), A^C†òÚº:u

,...,u

ƒë]!:íØÚº:v

"-m= r+(1+a

)+(1+a

)+...+(1+a

)(m≥2 ,m+s≥2),t= a

(t≥1), d½n3.4



PS(G

(s,r,a

,...,a

)) ≥PS(G

(s,m,t))(6)

dÚn3.8

DOI:10.12677/pm.2021.11112161940nØêÆ

x=f

PS(G

(s,m,t)) = (6m+8t+4s)+(6tm+2ts+2ms)+2tms+14

PS(G

(s,m,t))−PS(G

(s+1,m−1,t)) = 2(t+1)(3+s−m)−2, ©ü«œ¹"

œ¹˜3+s>m,PS(G

(s,m,t)) >PS(G

(s+1,m−1,t)), 

PS(G

(s+m,0,t)) <PS(G

(s+m−1,1,t)) <···<PS(G

(s,m,t))

¤±PS(G

(s,m,t)) ≥PS(G

(s+m,0,t))"

œ¹3+s≤m,PS(G

(s,m,t)) <PS(G

(s+1,m−1,t)), 

PS(G

(0,s+m,t)) <PS(G

(1,s+m−1,t)) <···<PS(G

(s,m,t))

¤±PS(G

(s,m,t)) ≥PS(G

(0,s+m,t)))"

PS(G

(0,s+m,t)))−PS(G

(s+m,0,t)) = 2(m+s)(2t+1) >0"

¤±

PS(G

(s,m,t)) ≥PS(G

(s+m,0,t))(7)

(II)k= 1ž"

-m= r,m≥0"

d(7)ªPS(G

(s,m,t)) ≥PS(G

(s+m,0,t))"

PS(G

(s+m,0,t))−PS(G

(s+m+1,0,t−1)) = 2(m+s+3−t), ©ü«œ¹"

œ¹˜t≥m+s+3,PS(G

(s+m,0,t)) ≤PS(G

(s+m+1,0,t−1)), 

PS(G

(2,0,s+m−2)) ≤PS(G

(3,0,s+m−3)) ≤···≤PS(G

(s+m,0,t))"

¤±PS(G

(s+m,0,t)) ≥PS(G

(2,0,s+m−2)) = 12n−62"

œ¹t<m+s+3,PS(G

(s+m,0,t)) >PS(G

(s+m+1,0,t−1)), 

PS(G

(s+m−1,0,1)) ≤PS(G

(s+m−2,0,2)) ≤···≤PS(G

(s+m,0,t))

¤±PS(G

(s+m,0,t)) ≥PS(G

(s+m−1,0,1)) = 6n−14"

du12n−62 >6n−14, 

PS(G

(s+m,0,t) ≥6n−14(8)

(Ü(6)(7) Ú(8) PS(G

(s,r,a

,...,a

)) ≥6n−14"

Ún5.2PS(G

,r,a

,···,a

)) ≥5n−11"

y²(I)p

–˜‡Ø•0"

(i)k≥2 ž, éG

,r,a

,···,a

), A^C†òÚòÚº:v

ë]!:íØ

Úº:v

ë"2|^C†nòÚº:u

,...,u

ƒë]!:íØÚº:v

ë,éA

DOI:10.12677/pm.2021.11112161941nØêÆ

x=f

ãP•G

(s,t,m)"-p

= s,t= r+(a

+1)+(a

+1)+...(a

+1)(t≥2),a

= m(m≥1) ,

dÚn3.4ÚÚn3.7 

PS(G

,r,a

,···,a

)) ≥PS(G

(s,t,m))(9)

dÚn3.8PS(G

(s,t,m)) = (m+1)(st+2s+2t+4)+s+2"

PS(G

(s,t,m))−PS(G

(s,t+1,m−1)) = (s+2)(t+2−m),©ü«œ¹"

œ¹˜m≤t+2,PS(G

(s,t,m)) ≥PS(G

(s,t+1,m−1)), 

PS(G

(s,t+m−1,1)) ≤PS(G

(s,t+m−2,2)) ≤···≤PS(G

(s,t,m))"

¤±PS(G

(s,t,m)) ≥PS(G

(s,t+m−1,1))"

œ¹m>t+2,PS(G

(s,t,m)) <PS(G

(s,t+1,m−1)), 

PS(G

(s,0,t+m)) <PS(G

(s,1,t+m−1)) ≤···≤PS(G

(s,t,m))"

¤±

PS(G

(s,t,m)) ≥PS(G

(s,t+m−1,1))(10)

(ii)k= 1,t≥0 ž"

dÚn3.8PS(G

(s,t,m)) = (m+1)(st+2s+2t+4)+s+2"d(10) 

PS(G

(s,t,m)) ≥PS(G

(s,t+m−1,1))"

PS(G

(s,t+m−1,1))−PS(G

(s−1,t+m,1)) = 2(m+t−s+1)−1, ©ü«œ¹"

œ¹˜s<m+t+1,PS(G

(s,t+m−1,1)) >PS(G

(s−1,t+m,1)), 

PS(G

(1,s+t+m−2,1)) <PS(G

(2,s+t+m−3,1)) <···<PS(G

(s,t+m−1,1))

¤±PS(G

(s,t+m−1,1)) ≥PS(G

(1,s+t+m−2,1)) = 6n−21"

œ¹s≥m+t+1,PS(G

(s,t+m−1,1)) <PS(G

(s−1,t+m,1)), 

PS(G

(s+t+m−1,0,1)) <PS(G

(s+t+m−2,1,1))) <···<PS(G

(s,t+m−1,1))

¤±PS(G

(s,t+m−1,1)) ≥PS(G

(s+t+m−1,0,1))) = 5n−11"

du6n−21 >5n−11, (Ü(8) Ú(9)(10)

PS(G

(s,t+m−1,1)) ≥5n−11(11)

(II)p

= p

= 0ž,

(i)k≥3 A^C†ò†º:u

,...,u

ë]!:íØÚº:v

ƒë, ãP•

2∗

(m,s,t),-r+(a

+1)+(a

+1)+...+(a

+1) = m,a

= s,a

= t(s≥1,t≥1,m≥2), d

DOI:10.12677/pm.2021.11112161942nØêÆ

x=f

Ún3.4

PS(G

,r,a

,···,a

)) ≥PS(G

2∗

(m,s,t))(12)

dÚn3.8PS(G

2∗

(m,s,t) = 2(m+3)(t+1)(s+1)+2(s+1)+2(t+1)"

PS(G

2∗

(m,s,t)−PS(G

2∗

(m+1,s−1,t) = 2[(t+1)(m+3−s)+1], ©ü«œ¹"

œ¹˜s≤m+3,PS(G

2∗

(m,s,t) >PS(G

2∗

(m+1,s−1,t), 

PS(G

2∗

(m+s−1,1,t) <PS(G

2∗

(m+s−2,2,t) <···<PS(G

2∗

(m,s,t)

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(m+s−1,1,t)"

œ¹s>m+3,PS(G

2∗

(m,s,t) <PS(G

2∗

(m+1,s−1,t), 

PS(G

2∗

(2,m+s−2,t) <PS(G

2∗

(3,m+s−3,t) <···<PS(G

2∗

(m,s,t)

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(2,m+s−2,t)"

PS(G

2∗

(2,m+s−2,t)−PS(G

2∗

(m+s−1,1,t) = 2(3t+4)(m+s−3) ≥0"

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(m+s−1,1,t)"

(ii)k= 2 ž,r= m≥0,a

= s,a

= t

dÚn3.8PS(G

2∗

(m,s,t) = 2(m+3)(t+1)(s+1)+2(s+1)+2(t+1)"

PS(G

2∗

(m,s,t)−PS(G

2∗

(m+1,s−1,t) = 2[(t+1)(m+3−s)+1], ©ü«œ¹"

œ¹˜s≤m+3,PS(G

2∗

(m,s,t) >PS(G

2∗

(m+1,s−1,t), 

PS(G

2∗

(m+s−1,1,t) <PS(G

2∗

(m+s−2,2,t) <···<PS(G

2∗

(m,s,t)

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(m+s−1,1,t)"

œ¹s>m+3,PS(G

2∗

(m,s,t) <PS(G

2∗

(m+1,s−1,t), 

PS(G

2∗

(0,m+s,t) <PS(G

2∗

(1,m+s−1,t) <···<PS(G

2∗

(m,s,t)

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(0,m+s,t)"

PS(G

2∗

(0,m+s,t)−PS(G

2∗

(m+s−1,1,t) = 2(t+2)(m+s−1) ≥0"

¤±PS(G

2∗

(m,s,t) ≥PS(G

2∗

(m+s−1,1,t)"

¤±nÜ(i)Ú(ii)

PS(G

2∗

(m,s,t) ≥PS(G

2∗

(m+s−1,1,t)(13)

PS(G

2∗

(m+s−1,1,t)−PS(G

2∗

(m+s,1,t−1) = 4(m+s−t)+10,©ü«œ¹"

œ¹˜m+s≥t−2,PS(G

2∗

(m+s−1,1,t) >PS(G

2∗

(m+s,1,t−1), 

PS(G

2∗

(m+s−2,1,1) <PS(G

2∗

(m+s−3,1,2) <···<PS(G

2∗

(m+s−1,1,t)

DOI:10.12677/pm.2021.11112161943nØêÆ

x=f

¤±

PS(G

2∗

(m+s−1,1,t) ≥PS(G

2∗

(m+s−2,1,1) = 8n−24(14)

œ¹m+s<t−2,PS(G

2∗

(m+s−1,1,t) <PS(G

2∗

(m+s,1,t−1), 

PS(G

2∗

(0,1,m+s−1) <PS(G

2∗

(1,1,m+s−2) <···<PS(G

2∗

(m+s−1,1,t)

¤±PS(G

2∗

(m+s−1,1,t) ≥PS(G

2∗

(0,1,m+s−1) = 14n−66"

Ï•14n−66 >8n−24, Šâ(11) (12)(13)(14)

PS(G

2∗

(m+s−1,1,t) ≥8n−24

du8n−24 >5n−11, (Ü(I) (II) (ØÑPS(G

) ≥5n−11"

Ún5.3PS(G

,r,a

,···,a

)) ≥6n−15"

y ²(I)p

–˜‡Ø•0 , ÏLCzn, ò†v

ƒ ë]!:íØÚº:v

ƒ ë"

2ÏLCzòu

,...,u

ƒë]!:íØÚº:v

ë"-p

=t,r+(a

+1)+(a

1)+...+(a

k−1

+1) = m,a

= s£t≥1,s≥1,m≥1,m+t+s+5 = n)"

dÚn3.4Ú3.6 PS(G

,r,a

,···,a

)) ≥PS(G

(s,m,t))"

dÚn3.8

PS(G

(s,m,t)) = (3m+3t+2mt+9)(s+1)+2t+3"

éG

(s,m,t)A^C†n,ò†º:v

ë]!:íKÚº:v

ëéAãP•

(s,m+t,0)"

dÚn3.6PS(G

(s,m,t)) ≥G

(s,m+t,0)"

éG

(s,m,t)A^C†n,ò†º:v

ë]!:íKÚº:v

ëéAãP•

(s,0,m+t)"

dÚn3.6PS(G

(s,m,t)) ≥G

(s,0,m+t)"

dÚn3.8G

(s,0,m+t)−G

(s,m+t,0) = 2(m+t) >0"

¤±PS(G

(s,m,t)) ≥G

(s,m+t,0)"

(II)p

= p

= 0ž,ÏLCzòu

,...,u

ƒë]!:íØÚº:v

ë"-p

t= 0,r+(a

+1)+(a

+1)+...+(a

k−1

+1) = m,a

= s£s≥1,m≥1,m+t+s+5 = n)"

dÚn3.6PS(G

(s,m,t)) ≥G

(s,m,0) = G

(s,m+t,0)"

dÚn3.8

PS(G

(s,m+t,0)) = (9+3m+3t)(s+1)+3,PS(G

(s,m+t,0))−PS(G

(s−1,m+t+1,0)) =

œ¹˜s≤m+t+3,PS(G

(s,m+t,0)) ≥PS(G

(s−1,m+t+1,0)),

PS(G

(1,m+t+s−1,0)) ≤PS(G

(2,m+t+s−2,0)) ≤···≤PS(G

(s,m+t,0))

DOI:10.12677/pm.2021.11112161944nØêÆ

x=f

¤±PS(G

(s,m+t,0)) ≥PS(G

(1,m+t+s−1,0)) = 6n−15"

œ¹s>m+t+3,PS(G

(s,m+t,0)) <PS(G

(s−1,m+t+1,0)),

PS(G

(s+m+t,0,0)) <PS(G

(s+m+t−1,1,0)) ≤···≤PS(G

(s,m+t,0))

¤±PS(G

(s,m+t,0)) ≥PS(G

(s+m+t,0,0)) = 9n−33"

du9n−33 >6n−15, ¤±PS(G

(s,m+t,0)) ≥PS(G

(1,m+t+s−1,0)) = 6n−15"

Ún5.4G

∼

),PS(G) ≥4n−8, Ò¤á…=G

∼

(1,m+t−1)"

y²éãG

)$^C†n,ò†v

ë]!:íØÚº:v

ë,-p

=m≥1,ò†v

ë]!:íØÚº:v

ë,-p

=t≥1,éAãP•

(m,t),m+t+4 = n"

dÚn3.6PS(G

)) ≥PS(G

(m,t))"

dÚn3.8

PS(G

(m,t)) = 3m+3t+mt+9,PS(G

(m,t))−PS(U

œ¹

œ¹˜t≤m+1ž, PS(G

(m,t)) ≥PS(G

(m+1,t−1)) ,

PS(G

(m+t−1,1)) <PS(G

(m+t−2,2)) <···<PS(G

(m,t))

¤±PS(G

(m,t)) ≥PS(G

(m+t−1,1)) = 4n−8"

œ¹t>m+1 ž,PS(G

(m,t)) <PS(G

(m+1,t−1)) ,

PS(G

(1,m+t−1)) <PS(G

(2,m+t−2)) <···<PS(G

(m,t))

¤±PS(G

(m,t)) ≥PS(G

(1,m+t−1)) = 4n−8"

Šâ(i)Ú(ii)PS(G

(m,t)) ≥4n−8"

PS(G

)) ≥4n−8"

Ún5.5PS(G

,r,a

,···,a

)) >5n−12"

y²éãG

,r,a

,···,a

)A^C†ÚC†nãG(5,n−5)"

dÚn3.4Ú3.6 PS(G

,r,a

,···,a

)) >PS(G(5,n−5))"

Ún5.6PS(G

)) >5n−12"

y²éãG

,r,a

,···,a

)A^C†nãG(5,n−5)"

dÚn3.6PS(G

,r,a

,···,a

)) >PS(G(5,n−5))"

Ún5.7PS(G

)) >5n−12"

y²éãG

)A^C†nãG(6,n−6)"

dÚn3.6PS(G

)) >PS(G(6,n−6))"

dÚn3.7PS(G(6,n−6)) >PS(G(5,n−5)) = 5n−12"

DOI:10.12677/pm.2021.11112161945nØêÆ

x=f

¤±PS(G

)) >5n−12"

Ún5.8PS(G

)) >5n−12"

y²éãG

)A^C†nãG(6,n−6)"

dÚn3.6PS(G

)) >PS(G(6,n−6))"

dÚn3.7PS(G(6,n−6)) >PS(G(5,n−5)) = 5n−12"

¤±PS(G

)) >5n−12"

Ún5.9PS(G

)) >5n−12"

y²éãG

)A^C†nãG(7,n−7)"

dÚn3.6PS(G

)) >PS(G(7,n−7))"

dÚn3.7PS(G(7,n−7)) >PS(G(6,n−6)) >PS(G(5,n−5)) = 5n−12"

¤±PS(G

)) >5n−12"

½n5.10 -G

(n)L«n‡º:†»•4 ¤küã8Ü,G∈G

(n),KPS(G)≥

4n−8, Ò¤á…=G

∼

(1,m+t−1))(„ã5)"

y²G∈G

(n),G

∼

(1,m+t−1)ž,dÚn4.1PS(G)=4n−8"G∈

(n)−{G

œ¹˜G

∼

(s,r,a

,...,a

),dÚn5.1PS(G

(s,r,a

,...,a

))≥6n−14>

4n−8"

œ¹G

∼

,r,a

,···,a

),dÚn5.2PS(G

,r,a

,···,a

))≥

5n−11 >4n−8"

œ¹nG

∼

,r,a

,···,a

),dÚn5.3PS(G

,r,a

,···,a

))≥

6n−15 >4n−8"

œ¹oG

∼

),dÚn5.4 PS(G) >4n−8"

œ¹ÊG

∼

,r,a

,···,a

),dÚn5.5PS(G

,r,a

,···,a

))>

5n−12 >4n−8"

œ¹8G

∼

),dÚn5.6 PS(G

)) >5n−12 >4n−8"

œ¹ÔG

∼

),dÚn5.7 PS(G

)) >5n−12 >4n−8"

œ¹lG

∼

),dÚn5.8 PS(G

)) >5n−12 >4n−8"

œ¹ÊG

∼

),dÚn5.9 PS(G

)) >5n−12 >4n−8"

¤±G∈G

(n),KPS(G) ≥4n−8, Ò¤á…=G

∼

(1,m+t−1))"

Ä7‘8

“°¬xŒÆïÄ)M#‘8,‘8?Ò:07M2021006"

DOI:10.12677/pm.2021.11112161946nØêÆ

x=f

ë•©z

[1]Merris, R., Rebman,K.R.andWatkins, W.(1981) Permanental Polynomialsof Graphs.Linear

AlgebraandItsApplications,38,273-288.https://doi.org/10.1016/0024-3795(81)90026-4

[2]Kasum, D., Trinajsti´c, N.andGutman, I.(1981) ChemicalGraph Theory.III.OnPermanental

Polynomial.CroaticaChemicaActa,54,321-328.

[3]Cash,G.G.(2000)ThePermanentalPolynomial.JournalofChemicalInformationandMod-

elingSciences,40,1203-1206.https://doi.org/10.1021/ci000031d

[4]Cash,G.G.(2000)PermanentalPolynomials of SmallerFullerenes. JournalofChemicalInfor-

mationandModelingSciences,40,1207-1209.https://doi.org/10.1021/ci0000326

[5]Chen, R. (2004)A Note on the Relations between the Permanental and Characteristic Polyno-

mials of CoronoidHydrocarbons. MATCHCommunicationsinMathematicalandinComputer

Chemistry,51,137-148.

[6]Chou,Q.,Liang,H.andBai,F.(2011)RemarksontheRelationsbetweenthePermanental

andCharacteristicPolynomialsofFullerenes.MATCHCommunicationsinMathematicaland

inComputerChemistry,66,743-750.

[7]Dehmer,M.,etal.(2017)HighlyUniqueNetworkDescriptorsBasedontheRootsofthe

PermanentalPolynomial.InformationSciences,408,176-181.

https://doi.org/10.1016/j.ins.2017.04.041

[8]Gutman,I.andCash,G.G.(2002)RelationsbetweenthePermanentalandCharacteristic

Polynomials ofFullerenes andBenzenoid Hydro-Carbons.MATCHCommunicationsinMath-

ematicalandinComputerChemistry,45,55-70.

[9]Liang,H.,Tong,H.andBai,F.(2008)ComputingthePermanentalPolynomialofC

Parallel.MATCHCommunicationsinMathematicalandinComputerChemistry,60,349-

358.

[10]Shi,Y.,Dehmer,M.,Li,X.andGutman,I.(2016)GraphPolynomials.CRCPress,Boca

Raton.https://doi.org/10.1201/9781315367996

[11]Wu,T.andLai,H.(2018)OnthePermanentalNullityandMatchingNumberofGraphs.

LinearandMultilinearAlgebra,66,516-524.https://doi.org/10.1080/03081087.2017.1302403

[12]Yan,W.andZhang,F.(2004)OnthePermanentalPolynomialofSomeGraphs.Journalof

MathematicalChemistry,35,175-188.https://doi.org/10.1023/B:JOMC.0000033254.54822.f8

[13]Yu, G.andQu,H.(2018)TheCoeﬃcientsoftheImmanantalPolynomial.AppliedMathematics

andComputation,339,38-44.https://doi.org/10.1016/j.amc.2018.06.057

[14]Zhang,H.and Li,W.(2012)Computingthe PermanentalPolynomials ofBipartiteGraphsby

PfaﬃanOrientation.DiscreteAppliedMathematics,160,2069-2074.

https://doi.org/10.1016/j.dam.2012.04.007

DOI:10.12677/pm.2021.11112161947nØêÆ

x=f

[15]Xie,S.,etal.(2004)CapturingtheLabileFullerene[50]asC

.Science,304,699.

https://doi.org/10.1126/science.1095567

[16]Tong,H.,Liang,H.andBai,F.(2006)PermanentalPolynomialsoftheLargerFullerenes.

MATCHCommunicationsinMathematicalandinComputerChemistry,56,141-152.

[17]Wu,T.andSo,W.(2019)UnicyclicGraphswithSecondLargestandSecondSmallestPer-

mantalSums.AppliedMathematicsandComputation,351,168-175.

https://doi.org/10.1016/j.amc.2019.01.056

[18]Chou,Q.,Liang,H.andBai,F.(2015)ComputingthePermanentalPolynomialoftheHigh

LevelFullereneC

withHighPrecision.MATCHCommunicationsinMathematicalandin

ComputerChemistry,73,327-336.

[19]Li,W.,Qin,Z.andZhang,H.(2016)ExtremalHexagonalChainswithRespecttotheCo-

eﬃcientsSumofthePermanentalPolynomial.AppliedMathematicsandComputation,291,

30-38.https://doi.org/10.1016/j.amc.2016.06.025

[20]Li,S.andWei,W.(2018)ExtremalOctagonalChainswithRespecttotheCoeﬃcientsSum

ofthePermanentalPolynomial.AppliedMathematicsandComputation,328,45-57.

https://doi.org/10.1016/j.amc.2018.01.033

[21]Wu,T.andLai,H.(2018)OnthePermanentalSumofGraphs.AppliedMathematicsand

Computation,331,334-340.https://doi.org/10.1016/j.amc.2018.03.026

[22]Li,W.,Qin,Z.andWang,Y.(2020)EnumerationofPermanentalSumsofLattice.Applied

MathematicsandComputation,370,ArticleID:124914.

https://doi.org/10.1016/j.amc.2019.124914

[23]Wu, T.and Lj,H. (2019)TheExtremalPermanentalSumforaQuasi-TreeGraph.Complexity,

2019,ArticleID:4387650.https://doi.org/10.1155/2019/4387650

[24]Wu, T., Ren, S. and Das, K.(2019) SomeExtremal Graphs withRespect to PermanentalSum.

BulletinoftheMalaysianMathematicalSciencesSociety,42,2947-2961.

https://doi.org/10.1007/s40840-018-0642-9

[25]Wu,T.andDas,K.(2020)OnthePermanentalSumofBicyclicGraphs.Computationaland

AppliedMathematics,39,ArticleNo.72.https://doi.org/10.1007/s40314-020-1108-x

[26]Hosoya,H. (1971)TopologicalIndex,a Newly ProposedQuantityCharacterizing the Topolog-

ical NatureofStructuralIsomersofSaturatedHydrocarbons.BulletinoftheChemicalSociety

ofJapan,44,2332-2339.https://doi.org/10.1246/bcsj.44.2332

[27]Feng,L.,Li,Z.,Liu,W.,Lu,L.andStevanovi´c,D.(2020)MinimalHarary IndexofUnicyclic

GraphswithDiameteratMost4.AppliedMathematicsandComputation,381,ArticleID:

125315.https://doi.org/10.1016/j.amc.2020.125315

[28]Wu,T.Z.andSo,W.(2019)UnicyclicGraphswithSecondLargestandSecondSmallest

PermanentalSums.AppliedMathematicsandComputation,351,168-175.

https://doi.org/10.1016/j.amc.2019.01.056

DOI:10.12677/pm.2021.11112161948nØêÆ