Minimal skew energy of oriented unicyclic graphs with a perfect matching

Abstract

Let $G^{\sigma }$ be an oriented graph of a simple undirected graph G with an orientation σ, which assigns to each edge of G a direction so that the resultant graph $G^{\sigma }$ becomes a directed graph. The skew energy of $G^{\sigma }$ is defined as the sum of the absolute values of all eigenvalues of the skew-adjacency matrix of $G^{\sigma }$. Denote by $U^{\sigma }(2k)$ the set of all oriented unicyclic graphs on 2k vertices with a perfect matching which contain no cycle of length l with $l\equiv 2(mod4)$. In this paper, we characterize the oriented graphs of $U^{\sigma }(2k)$ with the minimal skew energy for $k\ge 4$.

MSC:05C50, 15A30.

1 Introduction

Let G be a simple undirected graph on n vertices and $A(G)$ be its adjacency matrix. Let $Sp(G)=\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\}$ be the spectrum of $A(G)$. Then the energy of G, denoted by $E(G)$, is defined as $E(G)={\sum }_{i=1}^n|{\lambda }_i|$ (see [1]). The theory of graph energy is well developed nowadays. Its details can be found in the review [2] and recent book [3], and the references therein.

The skew energy of oriented graphs is a generalization for graph energy. First of all, we recall some definitions and notations. Let $G^{\sigma }$ be an oriented graph of a simple undirected graph G with the orientation σ, which assigns to each edge of G a direction so that the resultant graph $G^{\sigma }$ becomes an oriented graph or a directed graph. Then G is called the underlying graph of $G^{\sigma }$.

The skew-adjacency matrix $S(G^{\sigma })=(s_{ij})$ of $G^{\sigma }$ is a real skew symmetric matrix, where $s_{ij}=1$ and $s_{ji}=-1$ if $\overrightarrow{ij}$ is an arc of $G^{\sigma }$, otherwise $s_{ij}=s_{ji}=0$. The skew-spectrum $Sp(G^{\sigma })$ of $G^{\sigma }$ is defined as the spectrum of $S(G^{\sigma })$. Note that $Sp(G^{\sigma })$ consists of only purely imaginary eigenvalues because $S(G^{\sigma })$ is real skew symmetric. Shader and So [4] first studied the skew-spectrum of oriented graphs and obtained some results.

Analogous to the definition of the energy of a simple undirected graph, the skew energy of an oriented graph $G^{\sigma }$, proposed first by Adiga et al. [5] and denoted by $E_s(G^{\sigma })$, is defined as the sum of the absolute values of all eigenvalues of $S(G^{\sigma })$, that is, $E_s(G^{\sigma })={\sum }_{i=1}^n|s_i|$, where $s_1,s_2,\dots ,s_n$ are all the eigenvalues of $S(G^{\sigma })$. Recently, the skew energy of oriented graphs has been studied in [5–12].

The characteristic polynomial $det(xI-S(G^{\sigma }))$ of the skew-adjacency matrix $S(G^{\sigma })$ of an oriented graph $G^{\sigma }$ is also called the skew characteristic polynomial of $G^{\sigma }$, written as ${\varphi }_s(G^{\sigma },x)={\sum }_{i=0}^n{a}_i(G^{\sigma })x^{n-i}$. Since $S(G^{\sigma })$ is a real skew symmetric matrix, we have $a_{2i}(G^{\sigma })\ge 0$ and $a_{2i+1}(G^{\sigma })=0$ for all $0\le i\le \lfloor \frac{n}{2}\rfloor$ (see [5]). Then we have

$${\varphi }_s(G^{\sigma },x)=\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }{a}_{2i}\left(G^{\sigma }\right)x^{n-2i}.$$

(1)

Using equation (1), the skew energy $E_s(G^{\sigma })$ of an oriented graph $G^{\sigma }$ of order n can be expressed by the following integral formula [8]:

$$E_s\left(G^{\sigma }\right)=\frac{2}{\pi }{\int }_0^{+\mathrm{\infty }}\frac{1}{x^2}ln\left[\sum _{i=0}^{\lfloor n/2\rfloor }{a}_{2i}\left(G^{\sigma }\right)x^{2i}\right]dx.$$

(2)

Note that $a_0(G^{\sigma })=1$ and $a_2(G^{\sigma })$ equals the number of the edges of G. It follows that $E_s(G^{\sigma })$ is a strictly monotonically increasing function of those numbers $a_{2i}(G^{\sigma })$ ($i=1,\dots ,\lfloor \frac{n}{2}\rfloor$) for any oriented graphs. This in turn provides a way of comparing the skew energies of a pair of oriented graphs as follows.

Definition 1.1 Let $G_1^{{\sigma }_1}$ and $G_2^{{\sigma }_2}$ be two oriented graphs of order n. If $a_{2i}(G_1^{{\sigma }_1})\le a_{2i}(G_2^{{\sigma }_2})$ for all i with $1\le i\le \lfloor \frac{n}{2}\rfloor$, then we write $G_1^{{\sigma }_1}⪯G_2^{{\sigma }_2}$.

Furthermore, if $G_1^{{\sigma }_1}⪯G_2^{{\sigma }_2}$ and there exists at least one index j such that $a_{2j}(G_1^{{\sigma }_1})<a_{2j}(G_2^{{\sigma }_2})$, then we write that $G_1^{{\sigma }_1}\prec G_2^{{\sigma }_2}$. If $a_{2i}(G_1^{{\sigma }_1})=a_{2i}(G_2^{{\sigma }_2})$ for all i, we write $G_1^{{\sigma }_1}\sim G_2^{{\sigma }_2}$. According to the integral formula (2), we have for two oriented graphs $G_1^{{\sigma }_1}$ and $G_2^{{\sigma }_2}$ of order n that

$$\begin{array}{c}{G}_1^{{\sigma }_1}⪯G_2^{{\sigma }_2}⟹E_s\left(G_1^{{\sigma }_1}\right)\le E_s\left(G_2^{{\sigma }_2}\right),\hfill \\ G_1^{{\sigma }_1}\prec G_2^{{\sigma }_2}⟹E_s\left(G_1^{{\sigma }_1}\right)<E_s\left(G_2^{{\sigma }_2}\right).\hfill \end{array}$$

One of fundamental questions that is encountered in the study of skew energy is which oriented graphs from a given class have the maximal and minimal skew energy. In [4], Shader and So showed that $Sp(T^{\sigma })=iSp(T)$ for any n-vertex oriented tree $T^{\sigma }$, and thus $E_s(T^{\sigma })=E(T)$ which implies that $E_s(S_n^{\sigma })\le E_s(T^{\sigma })\le E_s(P_n^{\sigma })$, where $S_n^{\sigma }$ and $P_n^{\sigma }$ denote an oriented star and an oriented path with any orientation, respectively.

Using the method of quasi-order defined as above, some oriented graphs from a given class which have the maximal or minimal skew energy have been further characterized. Hou et al. [8] determined the oriented unicyclic graphs with the maximal and minimal skew energies. Zhu [12] further characterized the oriented unicyclic graphs with the first $\lfloor \frac{n-9}{2}\rfloor$ largest skew energies. Shen et al. [10] determined the oriented bicyclic graphs with the maximal and minimal skew energies. Recently, Gong et al. [6] determined the oriented connected graph on n vertices with m ($n\le m\le 2(n-2)$) arcs which have the minimal skew energy.

In this paper, we first present some recurrence relations of the skew characteristic polynomials of oriented graphs in Section 2. By using these recurrence relations, we then provide a new technique to compare the skew energies of a class of oriented graphs which can tackle the quasi-order incomparable problems in Section 3. Denote by $U^{\sigma }(2k)$ the set of all oriented unicyclic graphs on 2k vertices with a perfect matching which contain no cycle of length l with $l\equiv 2(mod4)$. We finally characterize the oriented graphs of $U^{\sigma }(2k)$ with the minimal skew energy for $k\ge 4$ in Section 4.

2 Some recurrence relations of the skew characteristic polynomials of oriented graphs

In this section, we will show some recurrence relations of the skew characteristic polynomials of oriented graphs which will be used in the next section.

Let $G^{\sigma }$ be an oriented graph and C be an undirected even cycle of G. Then C is said to be evenly oriented relative to the orientation σ if it has an even number of edges oriented in clockwise direction (and now it also has even number of edges oriented in anticlockwise direction, since C is an even cycle). Otherwise C is said to be oddly oriented.

A linear subgraph L of G is a disjoint union of some edges and some cycles in G. We call a linear subgraph L of G evenly linear if L contains no odd cycle. We denote by ${\mathcal{EL}}_{2i}(G)$ the set of all evenly linear subgraphs of G with 2i vertices. For an evenly linear subgraph $L\in {\mathcal{EL}}_{2i}(G)$, we denote by $p_e(L)$ the number of evenly oriented cycles in L relative to the orientation σ.

The following lemma characterizes the coefficients of skew characteristic of an oriented graph, which is analogous to the famous Sachs theorem [13] for an undirected graph.

Lemma 2.1 ([7])

Let $G^{\sigma }$ be an oriented graph with the skew characteristic polynomial ${\varphi }_s(G^{\sigma },x)={\sum }_{i=0}^{\lfloor \frac{n}{2}\rfloor }{a}_{2i}(G^{\sigma })x^{n-2i}$. Then

$$a_{2i}\left(G^{\sigma }\right)=\sum _{L\in {\mathcal{EL}}_{2i}(G)}{(-1)}^{p_e(L)}{2}^{c(L)},$$

(3)

where $p_e(L)$ is the number of evenly oriented cycles of L and $c(L)$ is the number of even cycles of L, respectively.

For convenience, we write ${\varphi }_s(G^{\sigma })={\varphi }_s(G^{\sigma },x)$ in what follows. From Lemma 2.1, we can get the recurrence relation of ${\varphi }_s(G^{\sigma })$ as follows.

Theorem 2.1 Let v be a vertex of $G^{\sigma }$. Then

$$\begin{array}{rcl}{\varphi }_s\left(G^{\sigma }\right)& =& x{\varphi }_s(G^{\sigma }-v)+\sum _{uv\in G}{\varphi }_s(G^{\sigma }-v-u)+2\sum _{v\in C\in Od(G^{\sigma })}{\varphi }_s(G^{\sigma }-C)\\ -2\sum _{v\in C\in Ev(G^{\sigma })}{\varphi }_s(G^{\sigma }-C),\end{array}$$

(4)

where $Od(G^{\sigma })$ and $Ev(G^{\sigma })$ denote the sets of all oddly oriented cycles and evenly oriented cycles of $G^{\sigma }$, respectively.

Proof The proof is similar to the proof of Theorem 2.4 in [7]. □

Using Theorem 2.1, we can easily derive the following corollary.

Corollary 2.1 Let v be a vertex of $G^{\sigma }$ that is on no even cycle in $G^{\sigma }$. Then

$${\varphi }_s\left(G^{\sigma }\right)=x{\varphi }_s(G^{\sigma }-v)+\sum _{uv\in G}{\varphi }_s(G^{\sigma }-v-u).$$

The coalescence of two oriented graphs $G^{\sigma }$ and $H^{\tau }$ with respect to vertex u in $G^{\sigma }$ and vertex v in $H^{\tau }$, denoted by $G_u^{\sigma }\cdot H_v^{\tau }$ (sometimes abbreviated as $G^{\sigma }\cdot H^{\tau }$), is the oriented graph obtained by identifying the vertices u and v. From Theorem 2.1, we can deduce the recurrence relation of ${\varphi }_s(G^{\sigma }\cdot H^{\tau })$ as follows.

Theorem 2.2

$${\varphi }_s(G^{\sigma }\cdot H^{\tau })={\varphi }_s\left(G^{\sigma }\right){\varphi }_s(H^{\tau }-v)+{\varphi }_s(G^{\sigma }-u)({\varphi }_s\left(H^{\tau }\right)-x{\varphi }_s(H^{\tau }-v)).$$

Proof By using (4) we can get

$$\begin{array}{rcl}{\varphi }_s(G^{\sigma }\cdot H^{\tau })& =& x{\varphi }_s(G^{\sigma }\cdot H^{\tau }-v)+\sum _{ru\in G}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-u-r)+\sum _{vt\in H}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-v-t)\\ +2\sum _{u\in C\in Od(G^{\sigma })}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-C)+2\sum _{v\in C\in Od(H^{\tau })}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-C)\\ -2\sum _{u\in C\in Ev(G^{\sigma })}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-C)-2\sum _{v\in C\in Ev(H^{\tau })}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-C).\end{array}$$

(5)

Moreover, it is easily checked that

$$\begin{array}{c}{\varphi }_s(G^{\sigma }\cdot H^{\tau }-v)={\varphi }_s(G^{\sigma }-u)\cdot {\varphi }_s(H^{\tau }-v),\hfill \\ {\varphi }_s(G^{\sigma }\cdot H^{\tau }-u-r)={\varphi }_s(G^{\sigma }-u-r)\cdot {\varphi }_s(H^{\tau }-v),\hfill \\ {\varphi }_s(G^{\sigma }\cdot H^{\tau }-v-t)={\varphi }_s(G^{\sigma }-u)\cdot {\varphi }_s(H^{\tau }-v-t),\hfill \\ {\varphi }_s(G^{\sigma }\cdot H^{\tau }-C)={\varphi }_s(G^{\sigma }-C)\cdot {\varphi }_s(H^{\tau }-v)(C\in G^{\sigma }),\hfill \\ {\varphi }_s(G^{\sigma }\cdot H^{\tau }-C)={\varphi }_s(H^{\tau }-C)\cdot {\varphi }_s(G^{\sigma }-u)(C\in H^{\tau }).\hfill \end{array}$$

(6)

Applying (6) to (5), we find that

$$\begin{array}{rcl}{\varphi }_s(G^{\sigma }\cdot H^{\tau })& =& x{\varphi }_s(G^{\sigma }-u)\cdot {\varphi }_s(H^{\tau }-v)+{\varphi }_s(H^{\tau }-v)({\varphi }_s\left(G^{\sigma }\right)-x{\varphi }_s(G^{\sigma }-u))\\ +{\varphi }_s(G^{\sigma }-u)({\varphi }_s\left(H^{\tau }\right)-x{\varphi }_s(H^{\tau }-v))\\ =& {\varphi }_s\left(G^{\sigma }\right){\varphi }_s(H^{\tau }-v)+{\varphi }_s(G^{\sigma }-u)({\varphi }_s\left(H^{\tau }\right)-x{\varphi }_s(H^{\tau }-v)).\end{array}$$

Thus we complete the proof. □

3 A new technique for comparing the skew energies of two oriented k-sun attaching graphs

In [14], Shan and Shao presented a new technique of directly comparing the energies of two k-claw attaching bipartite graphs. In this section, we apply the main idea of this technique to compare the skew energies of oriented graphs. Then we will present a new technique for comparing the skew energies of two oriented k-sun attaching graphs.

Let $k\ge 0$. The tree $S{u}_k$ of order $2k+1$ will be called the k-sun (see Figure 1), which can be obtained by inserting a new vertex on each edge of the star $S_{k+1}$.

Figure 1

The tree k -sun and the k -sun attaching graph ${\mathit{G}}_{\mathit{u}}\mathbf{(}\mathit{k}\mathbf{)}$ .

The coalescence of two graphs G and H with respect to vertex u in G and vertex v in H, denoted by $G_u\cdot H_v$ (sometimes abbreviated as $G\cdot H$), is the graph obtained by identifying the vertices u and v. In particular, if H is the k-sun and v is the vertex of degree k, then we write $G\cdot H=G_u(k)$, which is called the k-sun attaching graphs at u, see Figure 1. For any orientations ${\sigma }_1$, ${\sigma }_2$, ${\tau }_1$ and ${\tau }_2$, for the sake of simplicity, we always write $G_u^{{\sigma }_1}\cdot {(S{u}_k)}^{{\sigma }_2}={(G_u(k))}^{\sigma }=G_u^{\sigma }(k)$ and $H_v^{{\tau }_1}\cdot {(S{u}_k)}^{{\tau }_2}={(H_v(k))}^{\tau }=H_v^{\tau }(k)$.

From Theorem 2.2, we can get the recurrence relations of ${\varphi }_s(G_u^{\sigma }(k))$ and ${\varphi }_s(H_u^{\tau }(k))$ in what follows.

Lemma 3.1

$${\varphi }_s(G_u^{\sigma }(k))={(x^2+1)}^{k-1}((x^2+1){\varphi }_s\left(G^{{\sigma }_1}\right)+xk{\varphi }_s(G^{{\sigma }_1}-u)),$$

(7)

$${\varphi }_s(H_v^{\tau }(k))={(x^2+1)}^{k-1}((x^2+1){\varphi }_s\left(H^{{\tau }_1}\right)+xk{\varphi }_s(H^{{\tau }_1}-v)).$$

(8)

Proof By Theorem 2.2 we have

$${\varphi }_s(G_u^{\sigma }(k))={\varphi }_s\left(G^{{\sigma }_1}\right){(x^2+1)}^k+{\varphi }_s(G^{{\sigma }_1}-u)({\varphi }_s\left({(S{u}_k)}^{{\sigma }_2}\right)-x{(x^2+1)}^k).$$

(9)

From Corollary 2.1, we can show

$${\varphi }_s\left({(S{u}_k)}^{{\sigma }_2}\right)=x{(x^2+1)}^{k-1}(x^2+1+k).$$

(10)

Applying (10) to (9), we can obtain (7). Similarly, we can show (8). Then the results hold. □

In what follows, we write:

$$\begin{array}{c}S(H^{{\tau }_1},G^{{\sigma }_1})={\varphi }_s\left(H^{{\tau }_1}\right){\varphi }_s(G^{{\sigma }_1}-u)-{\varphi }_s(H^{{\tau }_1}-v){\varphi }_s\left(G^{{\sigma }_1}\right),\hfill \\ D=\{x>0\mid S(H^{{\tau }_1},G^{{\sigma }_1})>0\},\hfill \\ D^c=\{x>0\mid S(H^{{\tau }_1},G^{{\sigma }_1})\le 0\}.\hfill \end{array}$$

It is easily checked that $D\cup D^c=(0,+\mathrm{\infty })$.

Furthermore, we write

$$\begin{array}{c}{s}_k(x)=\frac{{\varphi }_s(H_v^{\tau }(k))}{{\varphi }_s(G_u^{\sigma }(k))}=\frac{(x^2+1){\varphi }_s(H^{{\tau }_1})+xk{\varphi }_s(H^{{\tau }_1}-v)}{(x^2+1){\varphi }_s(G^{{\sigma }_1})+xk{\varphi }_s(G^{{\sigma }_1}-u)},\hfill \\ s(x)=\frac{{\varphi }_s(H^{{\tau }_1}-v)}{{\varphi }_s(G^{{\sigma }_1}-u)}.\hfill \end{array}$$

Under the above notations, we have the following properties for the functions $s_k(x)$ and $s(x)$.

Lemma 3.2 Let $x>0$ be fixed. Then, for all $0\le l<k$, we have the following.

• (1) If $x\in D$, then $s(x)<s_k(x)<s_l(x)$.

• (2) If $x\in D^c$, then $s(x)\ge s_k(x)\ge s_l(x)$.

Proof Using the definitions and some simple calculations, we can deduce that

$$s_k(x)-s(x)=\frac{{(x^2+1)}^{k}S(H^{{\tau }_1},G^{{\sigma }_1})}{{\varphi }_s(G_u^{\sigma }(k)){\varphi }_s(G^{{\sigma }_1}-u)},$$

(11)

$$s_k(x)-s_l(x)=\frac{x{(x^2+1)}^{k+l-1}(l-k)S(H^{{\tau }_1},G^{{\sigma }_1})}{{\varphi }_s(G_u^{\sigma }(k)){\varphi }_s(G_u^{\sigma }(l))}.$$

(12)

Then the results follow easily from (11) and (12). □

The following result [12] illustrates an integral formula for the difference of the skew energies of two oriented graphs with the same order.

Lemma 3.3 Let ${\varphi }_s(H^{\tau },x)$ and ${\varphi }_s(G^{\sigma },x)$ be two skew characteristic polynomials of two oriented graphs $H^{\tau }$ and $G^{\sigma }$ with the same order. Then

$$E_s\left(H^{\tau }\right)-E_s\left(G^{\sigma }\right)=\frac{2}{\pi }{\int }_0^{+\mathrm{\infty }}ln\frac{{\varphi }_s(H^{\tau },x)}{{\varphi }_s(G^{\sigma },x)}dx.$$

In the following, we assume that G and H have the same order. From Lemma 3.3, we have

$$E_s(H_v^{\tau }(k))-E_s(G_u^{\sigma }(k))=\frac{2}{\pi }{\int }_0^{+\mathrm{\infty }}ln{s}_k(x)dx.$$

(13)

Combining Lemma 3.2 and Lemma 3.3, we can present a new technique for comparing the skew energies of two oriented k-sun attaching graphs in the following theorem.

Theorem 3.1 Let D, $D^c$, $s_k(x)$ and $s(x)$ be defined as above. Then, for $0\le l<k$,

$$\begin{array}{rcl}{\int }_{D}lns(x)dx+{\int }_{D^c}ln{s}_l(x)dx& \le & \frac{\pi }{2}(E_s(H_v^{\tau }(k))-E_s(G_u^{\sigma }(k)))\\ \le & {\int }_{D}ln{s}_l(x)dx+{\int }_{D^c}lns(x)dx.\end{array}$$

Proof Using (13) we have

$$\begin{array}{rl}\frac{\pi }{2}(E_s(H_v^{\tau }(k))-E_s(G_u^{\sigma }(k)))& ={\int }_0^{+\mathrm{\infty }}ln{s}_k(x)dx\\ ={\int }_{D}ln{s}_k(x)dx+{\int }_{D^c}ln{s}_k(x)dx.\end{array}$$

The result easily follows from Lemma 3.2. □

4 Minimal skew energy of oriented unicyclic graphs with a perfect matching

In this section, we always assume that the order of a graph is $n=2k$. A k-matching is a disjoint union of k edges in G. The number of k-matchings is denoted by $m(G,k)$. We agree that $m(G,0)=1$ and $m(G,k)=0$ ($k<0$).

With regard to the coefficients $a_{2i}(G^{\sigma })$ of an oriented unicyclic graph, Hou et al. [8] got the following lemma.

Lemma 4.1 ([8])

Let $G^{\sigma }\in U^{\sigma }(2k)$ and $C_l$ be the unique cycle of G. Then we have:

• (1) If l is odd, then $a_{2i}(G^{\sigma })=m(G,i)$.

• (2) If l is even and $C_l$ is oddly oriented, then $a_{2i}(G^{\sigma })=m(G,i)+2m(G-C_l,i-\frac{l}{2})$.

• (3) If l is even and $C_l$ is evenly oriented, then $a_{2i}(G^{\sigma })=m(G,i)-2m(G-C_l,i-\frac{l}{2})$.

From Lemma 4.1, we can see that the skew energy of $G^{\sigma }$ is independent of the orientation σ when l is odd. Thus, for convenience, we write $G^{\ast }$ as $G^{\sigma }$ when l is odd. Furthermore, when l is even and $C_l$ is oddly oriented relative to σ, we write $G^{+}$ as $G^{\sigma }$. When l is even and $C_l$ is evenly oriented relative to σ, we write $G^{-}$ as $G^{\sigma }$.

Denote by $U(2k)$ the set of all unicyclic graphs on 2k vertices with a perfect matching which contain no cycle of length l with $l\equiv 2(mod4)$. Let $A_1$, $B_1$, $B_2$, $B_3$ be the unicyclic graphs as shown in Figure 2. The following theorem is the main result of this section.

Figure 2

The unicyclic graphs ${\mathit{A}}_{\mathbf{1}}$ , ${\mathit{B}}_{\mathbf{1}}$ , ${\mathit{B}}_{\mathbf{2}}$ , ${\mathit{B}}_{\mathbf{3}}$ .

Theorem 4.1 Let $G^{\sigma }\in U^{\sigma }(2k)$ and $k\ge 4$. If $G^{\sigma }\ne B_2^{-}$, then $E_s(B_2^{-})<E_s(G^{\sigma })$.

In order to prove Theorem 4.1, we first outline the basic strategy of the proof. We classify the graphs in $U(2k)$ into the following classes. Let $B(2k)$ = {$G\in U(2k)\mid$ the length of the unique cycle of G is divisible by 4} and $A(2k)=U(2k)\mathrm{\setminus }B(2k)$.

Denote by $K(G)$ the number of perfect matchings of a graph G. We first quote the following basic property about the number of perfect matchings of unicyclic graphs.

Lemma 4.2 ([15])

Let $G\in U(2k)$. Then $K(G)=1$ or $K(G)=2$.

By Lemma 4.2, we can classify the graphs in $B(2k)$ into two classes as follows:

$$\begin{array}{c}{B}_1(2k)=\{G\in B(2k)\mid K(G)=1\},\hfill \\ D(2k)=\{G\in B(2k)\mid K(G)=2\}.\hfill \end{array}$$

Next, in order to further classify the graphs in $D(2k)$ into two classes, we introduce some notations in what follows.

Throughout this paper, we denote by $M(G)$ a perfect matching of a graph G. Let $\hat{G}=G-M(G)-S_0$, where $S_0$ is the set of isolated vertices in $G-M(G)$. We call $\hat{G}$ the capped graph of G and G the original graph of $\hat{G}$.

Denote by $\mathcal{E}(G)$ the edge set of a graph G. Let $G\in D(2k)$. Then $K(G)=2$. Since a tree contains at most one perfect matching, we can see that $\mathcal{E}(G-C_l)\cap \mathcal{E}(\hat{G})$ are the same under two different perfect matchings of G. Thus we can classify the graphs in $D(2k)$ into the following two classes:

$$\begin{array}{c}{B}_2(2k)=\{G\in D(2k)\mid \mathcal{E}(G-C_l)\cap \mathcal{E}(\hat{G})\ne \mathrm{\varnothing }\},\hfill \\ B_3(2k)=\{G\in D(2k)\mid \mathcal{E}(G-C_l)\cap \mathcal{E}(\hat{G})=\mathrm{\varnothing }\}.\hfill \end{array}$$

To conclude, it is easy to see that

$$U(2k)=A(2k)\cup B_1(2k)\cup B_2(2k)\cup B_3(2k),$$

and $A_1\in A(2k)$, $B_1\in B_1(2k)$, $B_2\in B_2(2k)$ and $B_3\in B_3(2k)$.

For $k\ge 4$, our basic strategy of the proof of Theorem 4.1 is to prove the following results (R₁)-(R₃) later:

(R₁)

• (1) $E_s(B_2^{-})<E_s(A_1^{\ast })$.

• (2) $E_s(B_2^{-})<E_s(B_1^{-})$.

• (3) $E_s(B_2^{-})<E_s(B_3^{-})$.

(R₂) Let $G^{\sigma }\in A^{\sigma }(2k)$. If $G^{\sigma }\ne A_1^{\ast }$, then $E_s(A_1^{\ast })<E_s(G^{\sigma })$.

(R₃)

• (1) Let $G^{\sigma }\in B_1^{\sigma }(2k)$. If $G^{\sigma }\ne B_1^{-}$, then $E_s(B_1^{-})<E_s(G^{\sigma })$.

• (2) Let $G^{\sigma }\in B_2^{\sigma }(2k)$. If $G^{\sigma }\ne B_2^{-}$, then $E_s(B_2^{-})<E_s(G^{\sigma })$.

• (3) Let $G^{\sigma }\in B_3^{\sigma }(2k)$. If $G^{\sigma }\ne B_3^{-}$, then $E_s(B_3^{-})<E_s(G^{\sigma })$.

It is easy to see that we can prove Theorem 4.1 by combining the above results (R₁)-(R₃). We will prove the results (R₁)-(R₃) in Sections 4.1 to 4.3, respectively.

4.1 The proof of (R₁)

By some simple calculations, we find that $A_1^{\ast }$ and $B_2^{-}$, $B_1^{-}$ and $B_2^{-}$, $B_3^{-}$ and $B_2^{-}$ are all quasi-order incomparable. We first prove the results (2) and (3) of (R₁) by Theorem 3.1.

Lemma 4.3 If $k\ge 3$, then $E_s(B_2^{-})<E_s(B_1^{-})$.

Proof Let $B_2^{-}=H_v^{-}(k-3)$ and $B_1^{-}=G_u^{-}(k-3)$ (see Figure 2). By some simple calculations, we have

$$\begin{array}{r}{\varphi }_s\left(H^{-}\right)=x^6+6x^4+6x^2,{\varphi }_s(H^{-}-v)=x^3(x^2+4),\\ {\varphi }_s\left(G^{-}\right)=x^6+6x^4+5x^2+1,{\varphi }_s(G^{-}-u)=x(x^4+3x^2+1).\end{array}$$

It is easily checked that $S(H^{-},G^{-})=-x^3(x^2-1)(x^4+5x^2+2)$ implying that $D=(0,1)$. From Theorem 3.1, we can deduce that for $k\ge 3$,

$$\begin{array}{c}\frac{\pi }{2}(E_s\left(B_2^{-}\right)-E_s\left(B_1^{-}\right))\hfill \\ \le {\int }_{D}ln{s}_0(x)dx+{\int }_{D^c}lns(x)dx\hfill \\ ={\int }_0^{1}ln\frac{x^6+6x^4+6x^2}{x^6+6x^4+5x^2+1}dx+{\int }_1^{+\mathrm{\infty }}ln\frac{x^4+4x^2}{x^4+3x^2+1}dx\hfill \\ \doteq -0.232562<0.\hfill \end{array}$$

Then $E_s(B_2^{-})<E_s(B_1^{-})$. □

Lemma 4.4 If $k\ge 4$, then $E_s(B_2^{-})<E_s(B_3^{-})$.

Proof Let $B_2^{-}=H_v^{-}(k-3)$ and $B_3^{-}=G_u^{-}(k-3)$ (see Figure 2). By some simple calculations we have

$$\begin{array}{c}{\varphi }_s\left(H^{-}\right)=x^6+6x^4+6x^2,{\varphi }_s(H^{-}-v)=x^3(x^2+4),\hfill \\ {\varphi }_s\left(G^{-}\right)=x^6+6x^4+6x^2,{\varphi }_s(G^{-}-u)=x(x^2+1)(x^2+2),\hfill \end{array}$$

which implies that $S(H^{-},G^{-})=-x^3(x^2-2)(x^4+6x^2+6)$. Then we have $D=(0,\sqrt{2})$. By Theorem 3.1, we can find that for $k\ge 6$,

$$\begin{array}{c}\frac{\pi }{2}(E_s\left(B_2^{-}\right)-E_s\left(B_3^{-}\right))\hfill \\ \le {\int }_{D}log{s}_3(x)dx+{\int }_{D^c}logs(x)dx\hfill \\ ={\int }_0^{\sqrt{2}}log\frac{x^6+10x^4+24x^2+6}{(x^2+1)(x^4+9x^2+12)}dx+{\int }_{\sqrt{2}}^{+\mathrm{\infty }}log\frac{x^2(x^2+4)}{(x^2+1)(x^2+2)}dx\hfill \\ \doteq -0.005535<0.\hfill \end{array}$$

When $k=4$ and $k=5$, we can have $E_s(B_2^{-})<E_s(B_3^{-})$ by some simple calculations. Consequently, $E_s(B_2^{-})<E_s(B_3^{-})$ for $k\ge 4$. □

By computing, we find that we cannot show that $E_s(B_2^{-})<E_s(A_1^{\ast })$ by the above method. Thus we use an alternate method to prove the result.

Lemma 4.5 If $k\ge 3$, then $E_s(B_2^{-})<E_s(A_1^{\ast })$.

Proof When $k=3,4,5$, we can get $E_s(B_2^{-})<E_s(A_1^{\ast })$ by some direct calculations. Then in what follows we assume that $k\ge 6$. By Corollary 2.1 we have

$$\begin{array}{c}{\varphi }_s(A_1^{\ast },x)={(x^2+1)}^{k-2}(x^4+(k+2)x^2+1),\hfill \\ {\varphi }_s(B_2^{-},x)=x^2{(x^2+1)}^{k-4}(x^6+(k+4)x^4+4k{x}^2+6).\hfill \end{array}$$

Since the roots of ${\varphi }_s(A_1^{\ast },x)$ and ${\varphi }_s(B_2^{-},x)$ are purely imaginary, we can take $x=i\lambda$, which implies that

$$\begin{array}{c}{\varphi }_s(A_1^{\ast },i\lambda )={(1-{\lambda }^2)}^{k-2}({\lambda }^4-(k+2){\lambda }^2+1)={(1-{\lambda }^2)}^{k-2}f\left({\lambda }^2\right),\hfill \\ {\varphi }_s(B_2^{-},i\lambda )={\lambda }^2{(1-{\lambda }^2)}^{k-4}({\lambda }^6-(k+4){\lambda }^4+4k{\lambda }^2-6)={\lambda }^2{(1-{\lambda }^2)}^{k-4}g\left({\lambda }^2\right),\hfill \end{array}$$

where $f(\lambda )={\lambda }^2-(k+2)\lambda +1$ and $g(\lambda )={\lambda }^3-(k+4){\lambda }^2+4k\lambda -6$.

Let $x_1>x_2$ be the roots of $f(\lambda )$ and $y_1>y_2>y_3$ be the roots of $g(\lambda )$. Then

$$\begin{array}{c}{E}_s\left(A_1^{\ast }\right)=2(k-4)+2(\sqrt{x_1}+\sqrt{x_2}+2),\hfill \\ E_s\left(B_2^{-}\right)=2(k-4)+2(\sqrt{y_1}+\sqrt{y_2}+\sqrt{y_3}).\hfill \end{array}$$

Thus we only need to prove that $\sqrt{y_1}+\sqrt{y_2}+\sqrt{y_3}<\sqrt{x_1}+\sqrt{x_2}+2$ for $k\ge 6$. By some calculations we get

$$\begin{array}{c}g(0)=g(4)=-6<0,\hfill \\ g\left(\frac{2}{k}\right)=\frac{8}{k^3}+2-(\frac{4}{k}+\frac{16}{k^2})>0,\hfill \\ g(k+\frac{1}{2})=(k+\frac{1}{2})(\frac{k}{2}-\frac{7}{4})-6>0.\hfill \end{array}$$

It follows that $y_3<\frac{2}{k}$, $y_2<4$ and $y_1<k+\frac{1}{2}$ implying that

$$\sqrt{y_1}+\sqrt{y_2}+\sqrt{y_3}<\sqrt{\frac{2}{k}}+\sqrt{k+\frac{1}{2}}+2.$$

Moreover,

$$\sqrt{x_1}+\sqrt{x_2}=\sqrt{x_1+x_2+2\sqrt{x_1{x}_2}}=\sqrt{k+4},$$

which implies that we only need to show

$$\sqrt{\frac{2}{k}}+\sqrt{k+\frac{1}{2}}<\sqrt{k+4}.$$

(14)

In fact, it is easily checked that $\frac{17}{4}{k}^2-18k+4>0$ for $k\ge 6$, which implies (14). Thus we have completed the proof. □

Proof of (R ₁ ) The result can be directly derived from Lemmas 4.3, 4.4 and 4.5. □

4.2 The proof of (R₂)

Let $G\in U(2k)$. Firstly, we show a method of computing the matching number of G. It is easy to see that $\mathcal{E}(G)=\mathcal{E}(\hat{G})\cup M(G)$. Thus each i-matching Ω of G can be partitioned into two parts: $\mathrm{\Omega }=\mathrm{\Phi }\cup \mathrm{\Psi }$, where $\mathrm{\Phi }\subseteq \mathcal{E}(\hat{G})$ and $\mathrm{\Psi }\subseteq M(G)$. Let $r_j^{(2i)}(G)$ be the number of ways to choose i independent edges in G such that just j edges are in $\hat{G}$. For example, $r_0^{(2i)}(G)=\left(\begin{array}{c}k\\ i\end{array}\right)$ and $r_1^{(2i)}(G)=k\left(\begin{array}{c}k-2\\ i-1\end{array}\right)$.

Thus we have

$$m(G,i)=\sum _{j=0}^i{r}_j^{(2i)}(G)=p+\sum _{j=2}^i{r}_j^{(2i)}(G),$$

where $p=\left(\begin{array}{c}k\\ i\end{array}\right)+k\left(\begin{array}{c}k-2\\ i-1\end{array}\right)$.

Proof of (R ₂ ) Let $G^{\sigma }\in A^{\sigma }(2k)$. By Lemma 4.1 we have $a_{2i}(G^{\sigma })=m(G,i)$. Furthermore, since ${\hat{A}}_1$ is a star of order $k+1$, we have ${\sum }_{j=2}^i{r}_j^{(2i)}(A_1)=0$. From Lemma 4.1 we can deduce that $a_{2i}(A_1^{\ast })=m(A_1,i)=p\le m(G,i)=a_{2i}(G^{\sigma })$. Because $G\ne A_1$, $a_4(A_1^{\ast })<a_4(G^{\sigma })$ implying that $E_s(A_1^{\ast })<E_s(G^{\sigma })$. □

4.3 The proof of (R₃)

We firstly quote and prove some lemmas which will be used in the proof of (R₃).

Lemma 4.6 Let G be a unicyclic graph of order n and $C_l$ be the unique cycle of G. If $l\equiv 0(mod4)$, then $E(G)=E_s(G^{-})$.

Proof Since $l\equiv 0(mod4)$, G is a bipartite unicyclic graph. Then we can assume that the characteristic polynomial of G is

$$\varphi (G,x)=\sum _{i=0}^{\lfloor \frac{n}{2}\rfloor }{(-1)}^i{b}_{2i}(G)x^{n-2i},$$

where $b_{2i}(G)\ge 0$. According to the famous Coulson integral formula for energy of a graph [2], we have

$$E(G)=\frac{2}{\pi }{\int }_0^{+\mathrm{\infty }}\frac{1}{x^2}ln[\sum _{i=0}^{\lfloor n/2\rfloor }{b}_{2i}(G)x^{2i}]dx.$$

(15)

From the Sachs theorem [13], we can easily get $b_{2i}(G)=m(G,i)-2m(G-C_l,i-\frac{l}{2})$. By Lemma 4.1 we have $a_{2i}(G^{-})=m(G,i)-2m(G-C_l,i-\frac{l}{2})$, which implies that $b_{2i}(G)=a_{2i}(G^{-})$. Combining (2) and (15), we can find that $E(G)=E_s(G^{-})$. □

In [16], Li et al. showed the following result.

Lemma 4.7 ([16])

• (1) Let $G\in B_1(2k)$. If $G\ne B_1$, then $E(B_1)<E(G)$.

• (2) Let $G\in B_2(2k)$. If $G\ne B_2$, then $E(B_2)<E(G)$.

• (3) Let $G\in B_3(2k)$. If $G\ne B_3$, then $E(B_3)<E(G)$.

Lemma 4.8 Let G be a bipartite unicyclic graph. Then $E_s(G^{-})<E_s(G^{+})$.

Proof Let $C_l$ be the unique cycle of G. From Lemma 4.1, we can see that

$$\begin{array}{c}{a}_{2i}\left(G^{-}\right)=m(G,i)-2m(G-C_l,i-\frac{l}{2}),\hfill \\ a_{2i}\left(G^{+}\right)=m(G,i)+2m(G-C_l,i-\frac{l}{2}),\hfill \end{array}$$

which implies that $a_{2i}(G^{-})\le a_{2i}(G^{+})$. $a_l(G^{-})<a_l(G^{+})$ yields that $E_s(G^{-})<E_s(G^{+})$. □

Now we can use Lemmas 4.6, 4.7 and 4.8 to prove the result (R₃) as follows.

Proof of (R ₃ ) We first prove the result (1) of (R₃). Let $G^{\sigma }\in B_1^{\sigma }(2k)$ and $C_l$ be the unique cycle of G. Then $l\equiv 0(mod4)$.

If $C_l$ is evenly oriented relative to σ, then $E_s(G^{\sigma })=E_s(G^{-})$. From Lemmas 4.6 and 4.7 we have $E_s(B_1^{-})=E(B_1)<E(G)=E_s(G^{-})=E_s(G^{\sigma })$. Then the result (1) holds.

If $C_l$ is oddly oriented relative to σ, then $E_s(G^{\sigma })=E_s(G^{+})$. Using Lemmas 4.6, 4.7 and 4.8, we can see that $E_s(B_1^{-})=E(B_1)\le E(G)=E_s(G^{-})<E_s(G^{+})=E_s(G^{\sigma })$. Then the result (1) holds.

The results (2) and (3) of (R₃) can be proved similarly. Thus we have completed the proof. □