# The Extremal Permanental Sum for a Quasi-Tree Graph

Authors: Tingzeng Wu; Huazhong Lü
Journal: Complexity
 (2019)

---

## Abstract

LetG be a graph and A(G) the adjacency matrix of G. The permanent of matrix (xI-A(G)) is called the permanental polynomial of G. The permanental sum of G is the sum of the absolute values of the coefficients of permanental polynomial of G. Computing the permanental sum is #p-complete. In this note, we prove the maximum value and the minimum value of permanental sum of quasi-tree graphs. And the corresponding extremal graphs are also determined. Furthermore,we also determine the graphs with the minimum permanental sum among quasi-tree graphs of order n and size m, where n-1≤m≤2n-3.


---

## Body

## 1. Introduction

Thepermanent of n×n matrix M=(bij)(i,j=1,2,…,n) is defined as(1)perM=∑σ∏i=1nbiσi,where the sum is taken over all permutations σ of {1,2,…,n}.LetG be a graph with n vertices and let A(G) be its adjacency matrix. Thepermanental polynomial of G is defined as(2)πG,x=perxI-AG=∑k=0nbkGxn-k,where I is the unit matrix of order n. Basic theory of permanental polynomials is well studied recently in [1–3] and the references therein. Kasum et al.[4] and Merris et al. [5] gave the coefficients of the permanental polynomial of G, i.e.,(3)bkG=-1k∑H2cH,0≤k≤n,where the sum is taken over all Sachs subgraphs H of G on k vertices and c(H) is the number of cycles in H. Recall that aSachs subgraph is a graph in which each component is a single edge or a cycle.Thepermanental sum of graph G, denoted by PS(G), can be defined as the summation of all absolute values of coefficients of permanental polynomial of G, i.e.,(4)PSG=∑i=0nbiG=∑i=0n∑H2cH.Thus, PS(G)=1 if G is an empty graph. Wu and So [6] have shown that computing permanental sum of a graph is #P-complete.The permanental sum of a graph was first considered by Tong [7]. In [8], Xie et al. captured a labile fullerene C50(D5h). Tong computed all 271 fullerenes in C50. In his study, Tong found that the permanental sum of C50(D5h) achieves the minimum among all 271 fullerenes in C50. He pointed that the permanental sum would be closely related to stability of molecular graphs. Recently, the permanental sum of a graph has received much attention. Li et al. [9] determined the extremal hexagonal chains with respect to permanental sum. Li and Wei [10] proved the lower and upper bounds for the permanental sum of an octagonal chain. Wu and Lai [11] systematically introduced the properties of permanental sum of a graph.A connected graphG is called aquasi-tree graph, if there exists a vertex u∗ in G such that G-u∗ is a tree. Let G be a quasi-tree graph with n vertices and m edges. Then n-1≤m≤2n-3, and the degree of u∗ in G equals m-n+2. Denote Gn={G:Gisaquasi-treegraphofordern}, and Gn,m={G:Gisaquasi-treegraphofordernandsizem}. As an important class of graphs, quasi-tree graphs have been widely studied. For the background and some known results about quasi-tree graphs, we refer the reader to [12–15].The purpose of this note is to investigate the properties of permanental sum of quasi-tree graphs. The note is organized as follows. In the next section, we review some previous results that will be needed in the sequel. In Section3, we discuss the permanental sum of quasi-tree graphs.


## 2. Some Preliminary

In this note, we only consider finite, undirected, and simple graph. LetG be a graph with vertex set V(G) and edge set E(G). Theneighborhood of vertex v∈V(G), denoted by NG(v), is the set of vertices adjacent to v. The graph that arises from G by deleting a vertex u∈V(G) or an edge uv∈E(G) will be denoted by G-u or G-uv. Let G+H denote the union of two vertex disjoint graphs G and H. For any positive integer l, lG denotes the union of l disjoint copies of G. The path, cycle, and star of order n are denoted by Pn, Cn and K1,n-1, respectively.Two edges ofG are said to beindependent if they are not adjacent in G. A k-matching of G is a set of k mutually independent edges. For an integer k≥0, let m(G,k) denote the number of k-matchings of a graph G. TheHosoya indexZ(G) of a graph G is defined to be the total number of matchings of G, that is,(5)ZG=∑k=0n/2mG,k,where n is the number of the vertices of the graph G. Some results on Hosoya indices were studied in [3, 16–18].Forn≥2, let F(n)=F(n-1)+F(n-2) denote the sequence of Fibonacci numbers, in particular, F(0)=0 and F(1)=1.Lemma 1 (see [10]).
LetG=T1∪T2∪…∪Tt be a forest with order n≥2 and t≥2, where Ti is a tree with ni vertices, i=1,2,…,t. Then Z(G)≤∏i=1t‍F(ni+1) with equality if and only if Ti≅Pni. Moreover Z(G)≤F(m1+1)F(m2+1), where m1+m2=n with equality if and only if G≅Pm1∪Pm2.
LetEk be the empty graph of order k. Denote ∨ the graph joint of two graphs, and ∪ the disjoint union of two graphs. The graphs Fnm=(K1,m-n+1∪E2n-m+3)∨E1 and Hnn+2=(C3∪En-4)∨E1 are shown in Figure 1[19].Figure 1
GraphsFnm and Hnn+2 in Lemma 2.Lemma 2 (see [19]).
LetBn,m be the set consisting of all graphs of order n and size m. For G∈Bn,m with n-1≤m≤2n-3,(6)ZFnm≤ZG.Equality holds if and only if G=Fnm, or Hnn+2 when m=n+2, where Graphs Fnm and Hnn+2 see Figure 1.By the definitions ofBn,m and Gn,m, we obtain that Gn,m⊂Bn,m. By Lemma 2, we have the following.Corollary 3.
LetG∈Gn,m be a quasi-tree graph with n-1≤m≤2n-3. Then(7)ZFnm≤ZG,where the equality holds if and only if G=Fnm.Lemma 4 (see [11]).
LettingT be a tree with order n≥1, then n≤PS(T)≤F(n+1), the first equality holds if and only if T≅K1,n-1, and the second equality holds if and only if T≅Pn.Lemma 5 (see [11]).
LetPn be a path with n vertices. Then(8)PSPn=1ifn=0,1ifn=1,Fn+1ifn≥2.Lemma 6 (see [11]).
The permanental sum of a graph satisfies the following identities:(i)
LetG and H be two connected graphs. Then(9)PSG∪H=PSGPSH.(ii)
Lete=uv be an edge of a graph G and C(e) the set of cycles containing e. Then(10)PSG=PSG-e+PSG-v-u+2∑Ck∈CePSG-VCk.(iii)
Letv be a vertex of a graph G and C(v) the set of cycles containing v. Then(11)PSG=PSG-v+∑u∈NGvPSG-v-u+2∑Ck∈CvPSG-VCk.By Lemma6, we have the following.Corollary 7.
LetG be a graph and e an edge of G. Then PS(G-e)<PS(G).


## 3. Main Results

In this section, we will investigate the properties of permanental sum of a quasi-tree graph.Theorem 8.
LetG∈Gn,m be a quasi-tree graph with n-1≤m≤2n-3. Then(12)m2-mn+m+n≤PSG,where the equality holds if and only if G≅Fnm.Proof.
By the definition of permanental sum of a graph, it can be known thatPS(G)=Z(G)+2w(G), where w(G) denotes the number of all Sachs graphs containing cycles of G. Checking G, we know that G has exactly dG(u∗)2 cycles and dG(u∗)=m-n+2. Thus dG(u∗)2=w(Fnm)≤w(G). By Corollary 3, we have PS(Fnm)≤PS(G) with equality if and only if G≅Fnm. By Lemma 6, we obtain that(13)PSFnm=PSK1,m-n+1+2n-3-mPSK1,m-n+1+m-n+1PSK1,m-n+1+2m-n+22=m2-mn+m+n.This completes the proof.Theorem 9.
LetG∈Gn. Then(14)PSG≤Fn+∑i=1n-1FiFn-i+2∑r=1n-2∑jr=1n-r-1FjrFn-r-jr,where the equality holds if and only if G≅G∗.Proof.
LetG∈Gn, and let u∈NG(u∗) and CG(u∗)={C:Cisacyclecontainingu∗inG∈Gn}. Suppose that G∈Gn has the maximum permanental sum. We will characterize the structure of G. By (iii) of Lemma 6, it can be known that if G∈Gn has the maximum permanental sum, then PS(G-u∗), ∑u∗∈NG(v)PS(G-u∗-u), and ∑Ck∈C(u∗)PS(G-V(Ck)) must attain maximum value. From the definition of a quasi-tree graph, we know that G-u∗ is a tree. By Lemma 4, G-u∗ has the maximum permanental sum when G-u∗ is isomorphic to path Pn-1. Since a path has exactly two vertices of degree 1. Thus there exist exactly two vertices, say u′ and u′′, such that G-u∗-u′ and G-u∗-u′′ are paths. Set u∈NGu∗-u′,u′′. By Lemma 1, only when G-u∗-u has two components, each of which is a path, does ∑u∈NG(u∗)-{u′,u′′}PS(G-u∗-u) attain the maximum value. Similarly, by Lemma 1 and Lemma 6, ∑Ck∈C(u∗)PS(G-V(Ck)) attains the maximum value if and only if G-V(Ck) has two components, each of which is a path, and G has the largest number of cycles in Gn. Combining arguments above and Corollary 7, G must be isomorphic to G∗(see Figure 2). Let the number of 3-cycles, 4-cycles,..., n-cycles in G∗ be j1,j2,...,jr,...,jn-3,jn-2, respectively. By Lemma 6, we obtain that(15)PSG∗=PSPn-1+∑i=1n-1PSPi-1PSPn-1-i+2∑j1=1n-2PSPj1-1PSPn-2-j1+∑j2=1n-3PSPj2-1PSPn-3-j2+∑j3=1n-4PSPj3-1PSPn-4-j3+...+∑jn-3=12PSPjn-3-1PSPn-n-2-jn-3+PSPjn-2-1PSPn-n-1-jn-2=PSPn-1+∑i=1n-1PSPi-1PSPn-1-i+2∑r=1n-2∑jr=1n-r-1PSPjr-1PSPn-r-1-jr=Fn+∑i=1n-1FiFn-i+2∑r=1n-2∑jr=1n-r-1FjrFn-r-jr.Figure 2
GraphG∗.By Theorems8 and 9, we obtain the following result.Theorem 10.
LetG∈Gn. Then(16)n≤PSG≤Fn+∑i=1n-1FiFn-i+2∑r=1n-2∑jr=1n-r-1FjrFn-r-jr,The first equality holds if and only if G≅K1,n-1, and the second equality holds if and only if G≅G∗.



---

*Source: 4387650-2019-05-20.xml*