Solution to a Conjecture on the Permanental Sum ^†

Abstract

Let G be a graph with n vertices and m edges. $A\left(G\right)$ and I denote, respectively, the adjacency matrix of G and an n by n identity matrix. For a graph G, the permanent of matrix $(I+A(G\left)\right)$ is called the permanental sum of G. In this paper, we give a relation between the Hosoya index and the permanental sum of G. This implies that the computational complexity of the permanental sum is $NP$-complete. Furthermore, we characterize the graphs with the minimum permanental sum among all graphs of n vertices and m edges, where $n+3\le m\le 2n-3$.

1. Introduction

The permanent of an n square matrix $M=\left[m_{ij}\right]$ with $i,j\in \{1,2,\dots ,n\}$ is defined as

$$\begin{array}{c}\hfill \mathrm{per}\left(M\right)=\sum _{\sigma \in {\mathsf{\Lambda }}_n}\prod _{i=1}^n{m}_{i\sigma \left(i\right)},\end{array}$$

where ${\mathsf{\Lambda }}_n$ denotes a symmetry group of order n. The computational complexity of the permanent of a matrix is #P-complete [1].

Let G be a graph on n vertices and m edges. Let $A\left(G\right)$ and I denote the adjacency matrix of G and an n by n identity matrix, respectively. The permanental polynomial of G is defined as

$$\begin{array}{c}\hfill \pi (G,x)=\mathrm{per}(xI-A\left(G\right))=\sum _{k=0}^n{b}_k\left(G\right)x^{n-k},\end{array}$$

where $b_k\left(G\right)$ denotes the kth coefficient of $\pi (G,x)$. In particular, $b_0\left(G\right)=1$. The permanental polynomials of graphs were first introduced in mathematics [2] and chemistry [3]. For more and additional information, see [4,5] and the references therein.

A Sachs graph G is a graph wherein each component is a single edge or a cycle. For a given an integer $k\ge 0$, $S_k\left(G\right)$ is the collection of all Sachs subgraphs $H_k$ of order k in G, and let $c\left(H\right)$ be the number of cycles in H. Merris et al. [2] gave a Sachs type result closely related to the coefficients of the permanental polynomial of G as below:

$$\begin{array}{c}\hfill b_k\left(G\right)={(-1)}^k\sum _{H\in S_k\left(G\right)}{2}^{c\left(H\right)},0\le k\le n.\end{array}$$

(1)

The permanental sum of G, written as $PS\left(G\right)$, is the sum of the absolute values of all coefficients of $\pi (G,x)$, i.e.,

$$\begin{array}{c}\hfill PS\left(G\right)=\sum _{k=0}^n\left|b_k\left(G\right)\right|=\sum _{k=0}^n\sum _{H\in S_k\left(G\right)}{2}^{c\left(H\right)}.\end{array}$$

(2)

Specifically, $PS\left(G\right)=1$ if G is an empty graph. Wu and So [6] give an explicit formula for permanental sums as follows:

$$\begin{array}{c}\hfill PS\left(G\right)=\mathrm{per}(I+A(G\left)\right),\end{array}$$

which implies that calculating the permanental sum is #P-complete. The permanental sum of a graph was first considered by Tong [7]. In [8], Xie et al. captured a labile fullerene $C_{50}\left(D_{5h}\right)$. Tong computed all 271 fullerenes in $C_{50}$. In his study, Tong found that the permanental sum of $C_{50}\left(D_{5h}\right)$ achieves the minimum among all 271 fullerenes in $C_{50}$. He pointed out that the permanental sum will be closely related to the stability of molecular graphs. For more information about permanental sums, see [9,10,11,12].

A k-matching in G is a set of k independent edges, and the number of k-matching is denoted by $m(G,k)$. The matching number of G, denoted by $\upsilon \left(G\right)$, is the maximum size of a matching in G. The Hosoya index $Z\left(G\right)$ is defined as the total number of matchings of G, i.e.,

$$\begin{array}{c}\hfill Z\left(G\right)=\sum _{k=0}^{\upsilon \left(G\right)}m(G,k).\end{array}$$

In 1971, the chemist Hosoya firstly introduced $Z\left(G\right)$ as a chemical application to describe the thermodynamic properties of saturated hydrocarbons. Later, the computational complexity of $Z\left(G\right)$ was proved to be NP-complete [13,14]. Next, we introduce a relationship between the Hosoya index and the permanent below.

Theorem 1. 

Let G be a graph with n vertices, and let $\mathcal{C}$ be the collection for which elements $H^{\prime }$ are disjoint unions of cycles in G. Then

$$PS\left(G\right)=Z\left(G\right)+\sum _{H^{\prime }\in \mathcal{C}}{2}^{c\left(H^{\prime }\right)}Z(G-H^{\prime }).$$

(3)

Proof. 

By (1), we have

$$\begin{array}{c}\hfill |b_k\left(G\right)|=\sum _{H\in S_k\left(G\right)}{2}^{c\left(H\right)},0\le k\le n.\end{array}$$

Denote by $H_k^1$ a Sachs subgraph of G with k vertices such that each component is a single edge. Similarly, denote by $H_k^2$ a Sachs subgraph of G with k vertices such that at least one component is a cycle. Set $b_k^1\left(G\right)={\displaystyle \sum _{H_k^1\subset S_k\left(G\right)}}{2}^{c\left(H_k^1\right)}$ and $b_k^2\left(G\right)={\displaystyle \sum _{H_k^2\subset S_k\left(G\right)}}{2}^{c\left(H_k^2\right)}$, where $b_k^1\left(G\right)=0$ if k is odd. Obviously, $|b_k\left(G\right)|=b_k^1\left(G\right)+b_k^2\left(G\right)$. Furthermore, we know that $b_{2k}^1\left(G\right)=m(G,k)$ for $k=0,1,2,\cdots ,\upsilon \left(G\right)$. Thus

$$\begin{array}{c}\hfill \sum _0^n{b}_k^1\left(G\right)=Z\left(G\right).\end{array}$$

Assume that $H^{\prime }$ is disjoint cycles with i vertices, and $H^{\prime }\in \mathcal{C}$. For an integer k, the number $H_k^2$ is equal to $m(G-H^{\prime },k-i)$. Thus,

$$\begin{array}{c}\hfill b_k^2\left(G\right)=\sum _{H^{\prime }\in \mathcal{C}}{2}^{c\left(H^{\prime }\right)}m(G-H^{\prime },k-i).\end{array}$$

Combining the arguments as above, we have

$$\begin{array}{c}\hfill PS\left(G\right)=\sum _{k=0}^n\left|b_k\left(G\right)\right|=\sum _{k=0}^n(b_k^1\left(G\right)+b_k^2\left(G\right))=Z\left(G\right)+\sum _{H^{\prime }\in \mathcal{C}}{2}^{c\left(H^{\prime }\right)}Z(G-H^{\prime }).\end{array}$$

□

By Theorem 1 and Jerrum’s result [13], we have:

Corollary 1. 

The computation of $PS\left(G\right)$ is $NP$-Complete.

Recently, some results on permanental sums were published. Let ${\mathcal{G}}_{n,m}$ be a collection of connected simple graphs of order n and size m. Furthermore, if graph $G\in {\mathcal{G}}_{n,m}$ and $m=n+i$, then G is called a tree, unicyclic graph, bicyclic graph, tricyclic graph, tetracyclic graph, ⋯, k-cyclic graph, where $i=-1,1,2,3,\cdots ,n-3$. In particular, every k-cyclic graph contains at least k cycles. Wu and Lai [15] determined the smaller bound of permanental sums of all unicyclic graphs in ${\mathcal{G}}_{n,n}$. And the corresponding extremal graphs $F_n^n$ were determined, where the graph of $F_n^n$ can be seen in Figure 1. Wu and Das [16] determined the lower bound of permanental sums of all bicyclic graphs in ${\mathcal{G}}_{n,n+1}$. And the corresponding extremal graphs $F_{n+1}^n$ were determined, where graph of $F_{n+1}^n$ can be seen in Figure 1. So et al. [6] characterized the lower bounds of the permanental sums of all tricyclic graphs in ${\mathcal{G}}_{n,n+2}$. And the corresponding extremal graphs $F_{n+2}^n$ were determined, where the graph of $F_{n+1}^n$ can be seen in Figure 1. According to the above results, So et al. [6] proposed a conjecture as follows.

Conjecture 1.

For $G\in {\mathcal{G}}_{n,m}$ with $n+3\le m\le 2n-3$, $PS\left(G\right)\ge PS\left(F_n^m\right)$, and the equality holds if and only if $G=F_n^m$. The graph of $F_n^m$ can be seen in Figure 1.

Figure 1. Graph of $F_n^m$.

Figure 1. Graph of $F_n^m$.

In this paper, we focus on Conjecture 1, and we give a solution as follows.

Theorem 2. 

Let $G\in {\mathcal{G}}_{n,m}$. If $n+3\le m\le 2n-3$, then $PS\left(G\right)\ge PS\left(F_n^m\right)$, where the equality holds if and only if $G\cong F_n^m$.

The rest of this paper is organized as follows. In Section 2, we present some definitions and properties of permanental sums of graphs. In Section 3, we first present some graph operations that can be considered to be graph transformations, and show we that the transformed graph, generally, will have a smaller permanental sum than the original graph. Furthermore, we give the proof of Theorem 2. In the final section, we give a summary of this paper, and some new problems regarding permanent sums are introduced.

2. Preliminaries

All graphs considered in this work are undirected, finite, and simple graphs. For notation and terminology not defined here, see [17].

Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. The degree of a vertex $v\in V\left(G\right)$ is denoted by $d\left(v\right)$. The neighborhood of vertex $v\in V\left(G\right)$, denoted by $N_G\left(v\right)$, is the set of vertices adjacent to v. For a subgraph H of G, let $G-V\left(H\right)$ (respectively, $G-E\left(H\right)$) denote the subgraph obtained from G by deleting the vertices and edges (respectively, deleting the edges) of H. In particular, if H is a vertex v (or an edge e), then $G-V\left(H\right)$ (or $G-E\left(H\right)$) is written as $G-v$ (or $G-e$). The path, cycle, and star of order n are denoted by $P_n$, $C_n$, and $S_n$, respectively. Let $G\cup 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.

Now we present some properties of permanental sums of graphs.

Lemma 1 

([15]). The permanental sum of a graph satisfies the following identities:

(i) 

Let G and H be two graphs. Then

$$\begin{array}{c}\hfill PS(G\cup H)=PS\left(G\right)PS\left(H\right).\end{array}$$

(ii) 

Let $uv$ be an edge of graph G, and $\mathcal{C}\left(uv\right)$ is the set of cycles containing $uv$. Then

$$\begin{array}{c}\hfill PS\left(G\right)=PS(G-uv)+PS(G-v-u)+2\sum _{C\in \mathcal{C}\left(uv\right)}PS(G-V\left(C\right)).\end{array}$$

(iii) 

Let v be a vertex of graph G, $N_G\left(v\right)$ be the set of neighbors of v, and $\mathcal{C}\left(v\right)$ be the set of cycles containing v. Then

$$\begin{array}{c}\hfill PS\left(G\right)=PS(G-v)+\sum _{u\in N_G\left(v\right)}PS(G-v-u)+2\sum _{C\in \mathcal{C}\left(v\right)}PS(G-V\left(C\right)).\end{array}$$

Lemma 2 

([18]). Let G be a connected simple graph with n vertices. Then $n\le PS\left(G\right)\le n!$. The left equality holds if and only if $G\cong S_n$, and the right equality holds if and only if $G\cong K_n$.

Lemma 3 

([6]). Let $G\in {\mathcal{G}}_{n,n+2}$. Then $PS\left(G\right)\ge PS\left(F_n^{n+2}\right)$, where the equality holds if and only if $G\cong F_n^{n+2}$.

Lemma 4 

([19]). Suppose that $G\in {\mathcal{G}}_{n,m}$, where $n+2\le m\le 2n-3$, and all cut edges are pendent edges incident with the same vertex. Then there exists an edge $uv$ in G such that the subgraphs $G-uv$ and $G-\{u,v\}$ are still connected.

3. Proof of Theorem 2

Before we prove Theorem 2, we introduce three graph operations that can be considered to be graph transformations, and we show that, generally, the transformed graph will have smaller permanental sum than the original graph.

Definition 1. 

Let u be a vertex of graph $G_0$. Denote by $G_1$ the graph obtained from $G_0$ and a tree T by attaching u to a vertex v of T. Denote by $G_2$ the graph obtained from $G_0$ and a star $S_{\left|T\right|}$ by attaching u to the center $v^{\prime }$ of $S_{\left|T\right|}$. We designate the transformation from $G_1$ to $G_2$ as type I.

Lemma 5 

([15]). Suppose that $G_1$ and $G_2$ are two graphs as defined by Definition 1. Then $PS\left(G_1\right)\ge PS\left(G_2\right)$, and the equality holds if and only if T is a star and v is the center of T.

Definition 2. 

Let $G_0$ be a graph of order of at least 2, and let $u,v\in G_0$. Denote by $G(s,t)$ the graph obtained from $G_0$ by attaching $s\ge 1$ and $t\ge 1$ pendant vertices to u and v, respectively. Denote by $G^{\prime }(s+t)$ the graph obtained from $G_0$ by attaching $s+t$ pendant vertices to u, and denote by $G^{″}(s+t)$ the graph obtained from $G_0$ by attaching $s+t$ pendant vertices to v. The resulting graphs $G(s,t)$, $G^{\prime }(s+t)$, and $G^{″}(s+t)$ are displayed in Figure 2. We designate the transformation from $G(s,t)$ to $G^{\prime }(s+t)$ or $G^{″}(s+t)$ as type $II$.

Lemma 6. 

Suppose that $G(s,t)$, $G^{\prime }(s+t)$, and $G^{″}(s+t)$ are three graphs defined as in Definition 2. Then $PS\left(G(s,t)\right)>PS\left(G^{\prime }(s+t)\right)$ or $PS\left(G(s,t)\right)>PS\left(G^{″}(s+t)\right)$.

Proof. 

By Lemma 1, deleting $e_1,...,e_s,h_1,...,h_t$ one by one in $G(s,t)$, we get that

$$\begin{array}{ccc}& & PS\left(G\right(s,t\left)\right)\hfill \\ & =& PS(G(s,t)-e_1)+PS(G(s,t)-u_1-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G(s-1,t)\right)+PS\left((s-1)K_1\right)PS(G(0,t)-u)\hfill \\ & =& PS\left(G\right(s-1,t\left)\right)+PS\left(G\right(0,t)-u)\hfill \\ & =& PS(G(s-1,t)-e_2)+PS(G(s-1,t)-u_2-u)+PS(G(0,t)-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G(s-2,t)\right)+PS\left((s-2)K_1\right)PS(G(0,t)-u)+PS(G(0,t)-u)\hfill \\ & =& PS\left(G\right(s-2,t\left)\right)+PS\left(G\right(0,t)-u)+PS\left(G\right(0,t)-u)\hfill \\ & =& PS\left(G\right(s-2,t\left)\right)+2PS\left(G\right(0,t)-u)\hfill \\ & =& ....\hfill \\ & =& PS(G(s-(s-1),t)-e_s)+PS(G(s-(s-1),t)-u_s-u)+(s-1)PS(G(0,t)-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G(0,t)\right)+PS(G(0,t)-u)+(s-1)PS(G(0,t)-u)\hfill \\ & =& PS\left(G\right(0,t\left)\right)+sPS\left(G\right(0,t)-u)\hfill \\ & =& PS(G(0,t)-h_1)+PS(G(0,t)-v_1-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G(0,t-1)\right)+PS\left((t-1)K_1\right)PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(G(0,t-1)\right)+PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS(G(0,t-1)-h_2)+PS(G(0,t-1)-v_2-v)+PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G(0,t-2)\right)+PS\left((t-2)K_1\right)PS(G_0-v)+PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(G(0,t-2)\right)+2PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& ....\hfill \\ & =& PS(G(0,t-(t-1))-h_t)+PS(G(0,t-(t-1))-v_t-v)+(t-1)PS(G_0-v)\hfill \\ & & +sPS\left(G\right(0,t)-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G_0\right)+PS(G_0-v)+(t-1)PS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+sPS(G(0,t)-u)\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G(0,t)-u-h_1)+PS(G(0,t)-u-v_1-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS\left(K_1\right)PS(G(0,t-1)-u)+PS\left((t-1)K_1\right)\hfill \\ & & \times PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G(0,t-1)-u)+PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G(0,t-1)-u-h_2)+PS(G(0,t-1)\hfill \\ & & -u-v_2-v)+PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS\left(K_1\right)PS(G(0,t-2)-u)+PS\left((t-2)K_1\right)\hfill \\ & & \times PS(G_0-u-v)+PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G(0,t-2)-u)+2PS(G_0-u-v)]\hfill \\ & =& ....\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G(0,t-(t-1))-u-h_t)\hfill \\ & & +PS(G(0,t-(t-1))-u-v_t-v))+(t-1)PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G_0-u)+PS(G_0-u-v)\hfill \\ & & +(t-1)PS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+s[PS(G_0-u)+tPS(G_0-u-v)]\hfill \\ & =& PS\left(G_0\right)+tPS(G_0-v)+sPS(G_0-u)+stPS(G_0-u-v).\hfill \end{array}$$

Similarly, by Lemma 1, deleting $e_1,...,e_s,h_1,...,h_t$ one by one in $G^{\prime }(s+t)$, we obtain that

$$\begin{array}{ccc}& & PS\left(G^{\prime }(s+t)\right)\hfill \\ & =& PS(G^{\prime }(s+t)-e_1)+PS(G^{\prime }(s+t)-u_1-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G^{\prime }(s+t-1)\right)+PS\left((s+t-1)K_1\right)PS(G_0-u)\hfill \\ & =& PS\left(G^{\prime }(s+t-1)\right)+PS(G_0-u)\hfill \\ & =& PS(G^{\prime }(s+t-1)-e_2)+PS(G^{\prime }(s+t-1)-u_2-u)+PS(G_0-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G^{\prime }(s+t-2)\right)+PS\left((s+t-2)K_1\right)PS(G_0-u)+PS(G_0-u)\hfill \\ & =& PS\left(G^{\prime }(s+t-2)\right)+PS(G_0-u)+PS(G_0-u)\hfill \\ & =& PS\left(G^{\prime }(s+t-2)\right)+2PS(G_0-u)\hfill \\ & =& ...\hfill \\ & =& PS(G^{\prime }(s+t-(s+t-1)-h_t)+PS(G^{\prime }(s+t-(s+t-1)-v_t-u)\hfill \\ & & +(s+t-1)PS(G_0-u)\hfill \\ & =& PS\left(K_1\right)PS\left(G_0\right)+PS(G_0-u)+(s+t-1)PS(G_0-u)\hfill \\ & =& PS\left(G_0\right)+PS(G_0-u)+(s+t-1)PS(G_0-u)\hfill \\ & =& PS\left(G_0\right)+(s+t)PS(G_0-u).\hfill \end{array}$$

By the symmetry of the calculation of $PS\left(G^{\prime }(s+t)\right)$, it is easy to obtain that

$$\begin{array}{c}\hfill PS\left(G^{″}(s+t)\right)=PS\left(G_0\right)+(s+t)PS(G_0-v).\end{array}$$

Direct calculation yields

$$\begin{array}{ccc}\hfill {\Delta }_1& =& PS\left(G(s,t)\right)-PS\left(G^{\prime }(s+t)\right)\hfill \\ & =& t\left[PS(G_0-v)-PS(G_0-u)+sPS(G_0-u-v)\right],\hfill \\ \hfill {\Delta }_2& =& PS\left(G(s,t)\right)-PS\left(G^{″}(s+t)\right)\hfill \\ & =& s\left[PS(G_0-u)-PS(G_0-v)+tPS(G_0-u-v)\right].\hfill \end{array}$$

If ${\Delta }_1\le 0$, then $PS\left(G(s,t)\right)\le PS\left(G^{\prime }(s+t)\right)$, and so $PS(G_0-u)\ge PS(G_0-v)$ + $sPS(G_0-u-v)$. Thus,

$$\begin{array}{ccc}\hfill {\Delta }_2& =& PS\left(G(s,t)\right)-PS\left(G^{″}(s+t)\right)\hfill \\ & \ge & s\left[PS(G_0-v)+sPS(G_0-u-v)-PS(G_0-v)+tPS(G_0-u-v)\right]\hfill \\ & =& s(s+t)PS(G_0-u-v)>0.\hfill \end{array}$$

If ${\Delta }_2\le 0$, $PS\left(G(s,t)\right)\le PS\left(G^{″}(s+t)\right)$, and so $PS(G_0-v)\ge PS(G_0-u)$ + $tPS(G_0-u-v)$. Hence,

$$\begin{array}{ccc}\hfill {\Delta }_1& =& PS\left(G(s,t)\right)-PS\left(G^{\prime }(s+t)\right)\hfill \\ & \ge & t\left[PS(G_0-u)+tPS(G_0-u-v)-PS(G_0-u)+sPS(G_0-u-v)\right]\hfill \\ & =& t(s+t)PS(G_0-u-v)>0.\hfill \end{array}$$

So $PS\left(G(s,t)\right)>PS\left(G^{\prime }(s+t)\right)$ or $PS\left(G(s,t)\right)>PS\left(G^{″}(s+t)\right).$ □

Definition 3. 

Let G and H be two disjoint connected graphs of order of at least 2 with $v\in V\left(G\right)$ and $u\in V\left(H\right)$. Denote by $G_1$ the graph obtained from the union of G and H by adding a new edge $uv$. Let $G_2$ denote the graph obtained from $G_1$ by deleting the edge $uv$ and identifying u with v to form a new vertex x and attaching a pendent vertex y to x. The resulting graphs $G_1$ and $G_2$ are displayed in Figure 3. We designate the transformation from $G_1$ to $G_2$ as type $III$.

Lemma 7. 

Let $G_1$ and $G_2$ be two graphs as defined by Definition 3. Then $PS\left(G_1\right)>PS\left(G_2\right)$.

Proof. 

By Lemma 1, we have

$$\begin{array}{ccc}& & PS\left(G_1\right)\hfill \\ & =& PS\left(G\right)PS\left(H\right)+PS(G-v)PS(H-u)\hfill \\ & =& 2PS(G-v)PS(H-u)+PS(G-v)\sum _{u^{\prime }\in N_H\left(u\right)}PS(H-\{u,u^{\prime }\})+2PS(G-v)\hfill \\ & & \times \sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right))+\sum _{v^{\prime }\in N_G\left(v\right)}PS(G-\{v,v^{\prime }\})PS(H-u)\hfill \\ & & +\sum _{v^{\prime }\in N_G\left(v\right)}PS(G-\{v,v^{\prime }\})\sum _{u^{\prime }\in N_H\left(u\right)}PS(H-\{u,u^{\prime }\})+2\sum _{v^{\prime }\in N_G\left(v\right)}PS(G-\{v,v^{\prime }\})\hfill \\ & & \times \sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right))+2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))PS(H-u)\hfill \\ & & +2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))\sum _{u^{\prime }\in N_H\left(u\right)}PS(H-\{u,u^{\prime }\})+4\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))\hfill \\ & & \sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right)).\hfill \end{array}$$

Similarly, by Definition 3, $G_2-x=(G-v)\cup (H-u)$, $N_{G_2}\left(x\right)=N_G\left(v\right)\cup N_H\left(u\right)\cup \left\{y\right\}$, and by Lemma 1, we get that

$$\begin{array}{ccc}& & PS\left(G_2\right)\hfill \\ & =& PS(G_2-xy)+PS(G_2-\{x,y\})\hfill \\ & =& PS(G_2-x)+\sum _{x^{\prime }\in N_{G_2}\left(x\right)/y}PS(G_2-\{x,x^{\prime }\})+2\sum _{C\in {\mathcal{C}}_{G_2}\left(x\right)}PS(G_2-V\left(C\right))\hfill \\ & & +PS(G_2-\{x,y\})\hfill \\ & =& 2PS(G-v)PS(H-u)+\sum _{x^{\prime }\in N_G\left(v\right)}PS(G-\{x,x^{\prime }\})+\sum _{x^{\prime }\in N_H\left(u\right)}PS(H-\{x,x^{\prime }\})\hfill \\ & & +2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))+2\sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right))\hfill \\ & =& 2PS(G-v)PS(H-u)+PS(H-u)\sum _{v^{\prime }\in N_{G\left(v\right)}}PS(G-\{v,v^{\prime }\})+PS(G-v)\hfill \\ & & \times \sum _{u^{\prime }\in N_H\left(u\right)}PS(H-\{u,u^{\prime }\})+2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))+2\sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right)).\hfill \end{array}$$

Thus

$$\begin{array}{ccc}& & PS\left(G_1\right)-PS\left(G_2\right)\hfill \\ & =& 2\sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right))(PS(G-v)-1)+2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))\hfill \\ & & \times (PS(H-u)-1)+\left[\sum _{v^{\prime }\in N_G\left(v\right)}PS(G-\{v,v^{\prime }\})+2\sum _{C\in {\mathcal{C}}_G\left(v\right)}PS(G-V\left(C\right))\right]\hfill \\ & & \times \left[\sum _{u^{\prime }\in N_H\left(u\right)}PS(H-\{u,u^{\prime }\})+2\sum _{C\in {\mathcal{C}}_H\left(u\right)}PS(H-V\left(C\right))\right]\hfill \\ & >& 0.\hfill \end{array}$$

□

Remark 1. 

For topological indices of graphs, they have similar graph operations as above. For example, the Hosoya index [19], Wiener index [20,21], etc.

Proof of Theorem 2. 

Suppose that $G\in {\mathcal{G}}_{n,m}$ when $n+3\le m\le 2n-3$. By repeatedly applying the transformations I, $II$, and $III$ and by Lemmas 5–7, we can obtain a graph $G^{\prime }$ from G such that all bridges are pendent edges incident with the same vertex and $PS\left(G^{\prime }\right)\le PS\left(G\right)$, where the equality holds if and only if $G^{\prime }\cong G$. Additionally, by Lemma 4, there exists an edge $uv$ in $G^{\prime }$ such that both $G^{\prime }-uv\in {\mathcal{G}}_{n,m-1}$ and $G^{\prime }-\{u,v\}$ are connected.

We use induction on m. Assume that $m=n+3$, i.e., $G^{\prime }$ is a tetracyclic graph. On the one hand,

$$\begin{array}{ccc}\hfill PS\left(F_n^{n+3}\right)& =& PS(F_n^{n+3}-uv)+PS(F_n^{n+3}-\{u,v\})+2\sum _{C\in \mathcal{C}\left(uv\right)}PS(F_n^{n+3}-V\left(C\right))\hfill \\ & =& PS\left(F_n^{n+2}\right)+PS\left(S_{n-2}\right)+2\times 4.\hfill \end{array}$$

On the other hand, since $G^{\prime }$ contains at least 4 cycles, $G^{\prime }-uv\in {\mathcal{G}}_{n,n+2}$, and $G^{\prime }-\{u,v\}$ is a connected graph of order $n-2$, then

$$\begin{array}{ccc}\hfill PS\left(G\right)& \ge & PS\left(G^{\prime }\right)\hfill \\ & =& PS(G^{\prime }-uv)+PS(G^{\prime }-\{u,v\})+2\sum _{C\in \mathcal{C}\left(uv\right)}PS(G^{\prime }-V\left(C\right))\hfill \\ & \ge & PS\left(F_n^{n+2}\right)+PS\left(S_{n-2}\right)+8\hfill \\ & =& PS\left(F_n^{n+3}\right),\hfill \end{array}$$

where the last inequality is derived from Lemmas 2 and 3. In order for the equalities to hold, all the inequalities above should be equalities. Then $G^{\prime }-uv\cong F_n^{n+2},G^{\prime }-\{u,v\}\cong S_{n-2},{\displaystyle \sum _{C\in \mathcal{C}\left(uv\right)}}PS(G^{\prime }-V\left(C\right))=4$ and $G\cong G^{\prime }$. So it is not hard to verify that $G\cong G^{\prime }\cong F_n^{n+3}$.

Suppose now that the statement holds for $m-1$$(m\ge n+4)$. We will prove this for m as follows. We have

$$\begin{array}{ccc}\hfill PS\left(F_n^m\right)& =& PS(F_n^m-uv)+PS(F_n^m-\{u,v\})+2\sum _{C\in \mathcal{C}\left(uv\right)}PS(F_n^m-V\left(C\right))\hfill \\ & =& PS\left(F_n^{m-1}\right)+PS\left(S_{n-2}\right)+2(m-n+1).\hfill \end{array}$$

Note that $G^{\prime }$ consists of at least $m-n+1$ cycles. It follows that $G^{\prime }-uv\in {\mathcal{G}}_{n,m-1}^{\prime }$, and $G^{\prime }-\{u,v\}$ is a connected graph of order $n-2$.

$$\begin{array}{ccc}\hfill PS\left(G\right)& \ge & PS\left(G^{\prime }\right)\hfill \\ & =& PS(G^{\prime }-uv)+PS(G^{\prime }-\{u,v\})+2\sum _{C\in \mathcal{C}\left(uv\right)}PS(G^{\prime }-V\left(C\right))\hfill \\ & \ge & PS\left(F_n^{m-1}\right)+PS\left(S_{n-2}\right)+2(m-n+1)\hfill \\ & =& PS\left(F_n^m\right),\hfill \end{array}$$

where the last inequality is derived from the induction hypothesis and Lemma 2. Similarly, to make the equalities hold, all of the inequalities above should be equalities. Then $G^{\prime }-uv\cong F_n^{m-1}$, $G^{\prime }-\{u,v\}\cong S_{n-2}$, ${\displaystyle \sum _{C\in \mathcal{C}\left(uv\right)}}PS(G^{\prime }-V\left(C\right))=m-n+1$ and $G\cong G^{\prime }$. Therefore, it is not hard to verify that $G\cong G^{\prime }\cong F_n^m$. Hence, the assertion holds for m. Consequently, it holds for all $n+3\le m\le 2n-3$.

This completes the proof.

□

4. Summary

In this paper, we prove that the computational complexity of a permanental sum is $NP$-complete. In particular, we determine the minimum value of permanental sums of all graphs with given n vertices and $n+3\le m\le 2n-3$ edges. This result promotes the study of permanental sums. It raises a lot of interesting questions, such as those related to determining the sharp bound of a permanental sum of all graphs in ${\mathcal{G}}_{n,m}$ if $n+3\le m\le 2n-3$ and questions regarding characterizing the bound of permanental sums of all graphs in ${\mathcal{G}}_{n,m}$ if $m>2n-3$, etc.

A permanent is a generalized matrix function that has important applications in chemistry [22,23,24]. A permanental sum is a derivative of a permanent, and it is a topological index proposed to explain special chemical phenomena from a mathematical point of view. The result in Theorem 2 is interesting for chemistry. In [25], the authors pointed out that every graph with a maximum degree that is no more than 4 has a chemical molecule corresponding to it. The result in Theorem 2 implies that the smaller bound of permanental sums of all chemical molecules is determined. And an interesting problem arises, i.e., characterizing the sharp bound of permanental sums of chemical molecules.

In conclusion, the above problems will guide us to continue our research.