Minimizing the Gutman Index among Unicyclic Graphs with Given Matching Number

Abstract

For a connected graph G with vertex set V, denote by d(v) the degree of vertex v and d(u, v) the distance between u and v. The value $\mathrm{Gut}\left(G\right)=\sum _{\{u,v\}\subseteq V}d\left(u\right)d\left(v\right)d(u,v)$ is called the Gutman index of G. Recently, the graph minimizing the Gutman index among unicyclic graphs with pendent edges was characterized. Denoted by $\mathbb{U}(n,m)$ the set of unicyclic graphs on n vertices with matching number m. Motivated by that work, in this paper, we obtain a sharp lower bound for Gutman index of graphs in $\mathbb{U}(n,m)$, and the extremal graph attaining the bound is also obtained. It is worth noticing that all the extremal graphs are of high symmetry, that is, they have large automorphic groups.

1. Introduction

Let G be a simple undirected graph on n vertices with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. The distance $d(v,u)$ of v and u is defined to be the length of a shortest path from u to v. The maximum value in the set $\left\{d\right(u,v)\mid v\in V(G\left)\right\}$ is called the eccentricity of u, denoted by $ecc\left(u\right)$. For $u\in V\left(G\right)$, write $d_G\left(u\right)$ (or just $d\left(u\right)$ for short if there is no confusion) for the degree of u in G, and $N\left(u\right)$ for the neighborhood of u.

For a molecular, if we let vertices represent the atoms and edges represent the bonds, then the resulting graph is called a molecular graph. So, a molecular graph could clearly reveal the corresponding molecular structure. Moreover, one could discover a molecule’s chemical properties by investigating its molecular graph’s combinatorial properties. A topological index for a molecular graph G is a numerical quantity invariant under automorphisms of G. Topological indices bridge chemical compounds’ physical, chemical, and thermodynamic parameters [1]. Up to now, researchers have defined many topological indices and used them to model chemical, pharmaceutical, and other properties of molecules. Nowadays, some novel computational techniques for topological indices have been developed, such as cut method, extended cut method, and vertex cut method, see, for example [2,3,4]. Such methods provide uniform way to deal with different topological indices. As one of the classic topological indices, the Wiener index is strongly related to many physical and chemical properties of molecular compounds (for the recent survey on the Wiener index see [5]). For all unordered pairs of distinct vertices of G, the summation of their distances is called the Wiener index of G and is denoted by $W\left(G\right)$, that is,

$$W\left(G\right)=\sum _{\{u,v\}\subseteq V\left(G\right)}d(u,v).$$

In 1994, Dobrynin and Kochetova [6], and Gutman [7] independently proposed a weighted version of the Wiener index as follows,

$$D^{\prime }\left(G\right)=\sum _{\{u,v\}\subseteq V\left(G\right)}(d\left(u\right)+d\left(v\right))d(u,v)=\sum _{v\in V\left(G\right)}d\left(v\right)·D_G\left(v\right)$$

(1)

where $D_G\left(v\right)={\sum }_{u\in V\left(G\right)}d(u,v).$ The value is also called the degree distance of G. It is interesting that, if G is a tree, then $D^{\prime }\left(G\right)=4W\left(G\right)-n(n-1)$ (see [7]).

In [7], another interesting index was also proposed, which is called the Schultz index of the second kind and also called the Gutman index somewhere (see [8] for example). It is defined to be

$$\mathrm{Gut}\left(G\right)=\sum _{\{u,v\}\subseteq V\left(G\right)}d\left(u\right)d\left(v\right)d(u,v).$$

Also, if G is a tree on n vertices, then $\mathrm{Gut}\left(G\right)=4W\left(G\right)-(2n-1)(n-1)$ (see [7]).

In [9], some extremal properties of the degree distance of graphs were reported. Dankelmann et al. [10] presented an asymptotically sharp upper bound of degree distance of graphs with given order and diameter. In [11], the authors determined the bicyclic graph with maximal degree distance. Ilić et al. [12] calculated the degree distance for partial Hamming graphs. In [13], Tomescu obtained the minimum degree distance of unicyclic and bicyclic graphs. The Gutman index of graphs attracts attention just recently, see, for example, [14,15,16,17]. The maximal and minimal Gutman index of bicyclic graphs were studied in [18,19]. In [20], the authors presented an asymptotic upper bound for the Gutman index and also established the relation between the edge-Wiener index and the Gutman index of graphs.

A unicyclic graph is a connected graph obtained from a tree by adding an edge connecting its two vertices. Denote by $C_n$ the cycle of n vertices. Let G be a unicyclic graph containing the cycle $C_k$. By deleting all edges in $C_k$, we obtain some disjoint trees. Each of these trees contains exactly one vertex of $C_k$, which is the root of such tree in G. These trees are called the branches of G. Let M be a subset of edges of G. If any pair of edges does not share a common vertex, then M is called a matching of G, and a vertex incident to some edge of M is said to be M-saturated. Particularly, if all vertices of G are M-saturated, then M is a perfect matching.

For integers $n\ge 4$ and m, $1\le m\le \lfloor \frac{n}{2}\rfloor$, let $\mathbb{U}(n,m)$ be the set of unicyclic graphs with n vertices and matching number m. Obviously, if $G\in \mathbb{U}(n,1)$, then G is the triangle. In the following we assume that $2\le m\le \lfloor \frac{n}{2}\rfloor$. Denote by $U_{n,m}$ the graph obtained by connecting $m-2$ new edges and $n-2m-1$ new vertices to a common vertex of the triangle $C_3$ (see Figure 1). Clearly, $U_{n,m}\in \mathbb{U}(n,m)$.

By immediate calculations, we have

$$\mathrm{Gut}\left(U_{n,m}\right)=2n^2+4mn-7n-8m+7,\mathrm{Gut}\left(U_{2m,m}\right)=16m^2-22m+7.$$

In this paper, we study the Gutman index of unicyclic graphs with given matching number and determine extremal graphs with the minimum Gutman index. On the one hand, we find that the graph minimizing the Gutman index among $\mathbb{U}(2m,m)$ plays an important role in dealing with $\mathbb{U}(n,m)$. So, we first deal with the special case of $\mathbb{U}(2m,m)$. On the other hand, we use induction method to deal with $\mathbb{U}(2m,m)$ instead of computational methods, which is very different from the earlier papers on this topic. Let $H_6$ be the graph obtained by attaching a pendant vertex to every vertex of a triangle, $H_7$ the graph obtained from $H_6$ by attaching one pendant vertex to a vertex of degree 3 in $H_6$, and let $H_8$ be the graph obtained by attaching three pendant vertices to three consecutive vertices of $C_5$ (see Figure 2). In fact, we obtain the following results.

Theorem 1.

Let $G\in \mathbb{U}(2m,m)$, where $m\ge 2$.

(i) 

If $m=3$, then $\mathrm{Gut}\left(G\right)\ge 81$ with equality if and only if $G\cong H_6$.

(ii) 

If $m\ne 3$, then $\mathrm{Gut}\left(G\right)\ge 16m^2-22m+7$ with equality if and only if $G\cong U_{2m,m}$.

Theorem 2.

Let $G\in \mathbb{U}(n,m)$, where $2\le m\le \lfloor \frac{n}{2}\rfloor$.

(i) 

If $(n,m)=(6,3)$, then $\mathrm{Gut}\left(G\right)\ge 81$ with equality if and only if $G\cong H_6$.

(ii) 

If $(n,m)\ne (6,3)$, then $\mathrm{Gut}\left(G\right)\ge 2n^2+4mn-7n-8m+7,$ with equality if and only if $G\cong H_7$ or $U_{7,3}$ for $(n,m)=(7,3)$; $G\cong U_{n,m}$ otherwise.

Note that, the extremal graphs for many indices, such as the spectral radius, the Wiener index, the Gutman index, and so on, are of high symmetry. It is interesting to investigate the inner relations between the symmetry of the graphs and their indices.

2. Main Results

Lemma 1

([21]). Let $G\in \mathbb{U}(2m,m)$, where $m\ge 3$, and let T be a branch of G with root r. If $u\in V\left(T\right)$ is a pendant vertex furthest from the root r with $d(u,r)\ge 2$, then u is adjacent to a vertex of degree two.

Lemma 2

([5]). Let $G\in \mathbb{U}(n,m)$, where $n>2m$, and let $G\ne C_n$. Then there is a maximum matching M and a pendant vertex u of G such that u is not M-saturated.

Lemma 3.

Let G be an n-vertex unicyclic graph with a pendant vertex u being adjacent to vertex v, and let w be a neighbor of v different from u. Then

$$\mathrm{Gut}\left(G\right)-\mathrm{Gut}(G-u)\ge -4d\left(v\right)+8n-5,$$

with equality if and only if $ecc\left(v\right)=2$; $d\left(x\right)=1$ for any $x\in V\left(G\right)\setminus \left(N\right(v)\cup \{u,v\left\}\right)$.

Moreover, if $d_G\left(v\right)=2,$ then

$$\mathrm{Gut}\left(G\right)-\mathrm{Gut}(G-u-v)\ge -8d\left(w\right)+20n-30,$$

with equality if and only if $ecc\left(w\right)=2$; $d\left(x\right)=1$ for any $x\in V\left(G\right)\setminus \left(N\right(w)\cup \{u,v,w\left\}\right)$.

Proof. 

From the definition, we have

$$\begin{array}{ccc}\mathrm{Gut}\left(G\right)\hfill & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v\}}d\left(x\right)d\left(y\right)d(x,y)+d\left(v\right)\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(v,x)\hfill \\ & & +d\left(u\right)\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(u,x)+d\left(v\right)\hfill \\ & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v\}}d\left(x\right)d\left(y\right)d(x,y)+(d_{G-u}\left(v\right)+1)\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(v,x)\hfill \\ & & +\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)(d(v,x)+1)+d\left(v\right)\hfill \\ & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v\}}d\left(x\right)d\left(y\right)d(x,y)+d_{G-u}\left(v\right)\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(v,x)\hfill \\ & & +\sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(v,x)+\sum _{x\in G\setminus \{u,v\}}d\left(x\right)(d(v,x)+1)+d\left(v\right)\hfill \\ & =\hfill & \mathrm{Gut}(G-u)+2\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)d(x,v)+2e\left(G\right)-1\hfill \\ & \ge \hfill & \mathrm{Gut}(G-u)+2\left(\sum _{x\in N\left(v\right)\setminus \left\{u\right\}}d\left(x\right)+\sum _{x\in V\left(G\right)\setminus \left(N\right(v)\cup \{v,u\left\}\right)}2d\left(x\right)\right)+2e\left(G\right)-1\hfill \\ & =\hfill & \mathrm{Gut}(G-u)+2\left(\sum _{x\in V\left(G\right)\setminus \{u,v\}}d\left(x\right)+\sum _{x\in V\left(G\right)\setminus \left(N\right(v)\cup \{v,u\left\}\right)}d\left(x\right)\right)+2e\left(G\right)-1\hfill \\ & \ge \hfill & \mathrm{Gut}(G-u)+2\left(2e\left(G\right)-d\left(v\right)-1+n-1-d\left(v\right)\right)+2e\left(G\right)-1\hfill \\ & =\hfill & \mathrm{Gut}(G-u)+6e\left(G\right)+2n-5-4d\left(v\right)\hfill \\ & =\hfill & \mathrm{Gut}(G-u)-4d\left(v\right)+8n-5,\hfill \end{array}$$

with equality if and only if $ecc\left(v\right)=2$; $d\left(x\right)=1$ for any $x\in V\left(G\right)\setminus \left(N\right(v)\cup \{,u\left\}\right)$.

Similarly, we have

$$\begin{array}{ccc}\mathrm{Gut}\left(G\right)\hfill & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d\left(y\right)d(x,y)+d\left(w\right)\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(w,x)\hfill \\ & & +d\left(v\right)\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(v,x)+d\left(u\right)\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(u,x)\hfill \\ & & +2d\left(w\right)+2d\left(w\right)+2\hfill \\ & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d\left(y\right)d(x,y)\hfill \\ & & +(d_{G-u-v}\left(w\right)+1)\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(w,x)\hfill \\ & & +2\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)(d(w,x)+1)\hfill \\ & & +\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)(d(w,x)+2)+4d\left(w\right)+2\hfill \\ & =\hfill & \sum _{\{x,y\}\subseteq V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d\left(y\right)d(x,y)+d_{G-u-v}\left(w\right)\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(w,x)\hfill \\ & & +4\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(w,x)+4\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)+4d\left(w\right)+2\hfill \\ & =\hfill & \mathrm{Gut}(G-u-v)+4\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)d(w,x)+4\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)\hfill \\ & & +4d\left(w\right)+2\hfill \\ & \ge \hfill & \mathrm{Gut}(G-u-v)+4\left(\sum _{x\in N\left(w\right)\setminus \left\{v\right\}}d\left(x\right)+2\sum _{x\in V\left(G\right)\setminus \left(N\right(w)\cup \{u,v,w\left\}\right)}d\left(x\right)\right)\hfill \\ & & +4d\left(w\right)+2\hfill \\ & =\hfill & \mathrm{Gut}(G-u-v)+4\sum _{x\in V\left(G\right)\setminus \{u,v,w\}}d\left(x\right)+4\sum _{x\in V\left(G\right)\setminus \left(N\right(w)\cup \{u,v,w\left\}\right)}d\left(x\right)\hfill \\ & & +4d\left(w\right)+2\hfill \\ & \ge \hfill & \mathrm{Gut}(G-u-v)+4(2e-1-2-d(w\left)\right)+4(n-2-d(w\left)\right)+4d\left(w\right)+2\hfill \\ & =\hfill & \mathrm{Gut}(G-u-v)+20n-8d\left(w\right)-30,\hfill \end{array}$$

with equality if and only if $ecc\left(w\right)=2$; $d\left(x\right)=1$ for any $x\in V\left(G\right)\setminus \left(N\right(w)\cup \{u,v,w\left\}\right)$.

We denote by $H_{n,k}$ the graph obtained from $C_k$ by adding $n-k$ pendant vertices to a vertex of $C_k$. In [18] it is obtained

$$\mathrm{Gut}\left(H_{n,k}\right)=\left\{\begin{array}{c}\frac{1}{2}\left(4n^2+(2k^2-4k-2)n-k^3+2k\right),\mathrm{if} k \mathrm{is} \mathrm{even};\hfill \\ \frac{1}{2}\left(4n^2+(2k^2-4k-4)n-k^3+3k\right),\mathrm{if} k \mathrm{is} \mathrm{odd}.\hfill \end{array}\right.$$

It is well known (see [22]) that

$$D_{C_k}\left(u\right)=\left\{\begin{array}{c}\frac{k^2}{4},\mathrm{if} k \mathrm{is} \mathrm{even};\hfill \\ \frac{k^2-1}{4},\mathrm{if} k \mathrm{is} \mathrm{odd}.\hfill \end{array}\right.$$

Let $U_n\left(k\right):=H$ be the unicyclic graph obtained from $C_k=v_1\dots v_k{v}_1$ by attaching a pendant vertex and $n-k-1$ pendant vertices to $v_1$ and $v_k$, respectively, where $3\le k\le n-2$. Suppose the neighbor of $v_1$ with degree 1 is w.

$$\begin{array}{ccc}\hfill \mathrm{Gut}\left(U_n\left(k\right)\right)& =& \sum _{x,y\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d\left(y\right)d(x,y)+d\left(w\right)\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,w)\hfill \\ & & +d\left(v_1\right)\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,v_1)+d\left(w\right)d\left(v_1\right)d(w,v_1)\hfill \\ & =& \sum _{x,y\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d\left(y\right)d(x,y)+\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)(d(x,v_1)+1)\hfill \\ & & +3\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,v_1)+3\hfill \\ & =& \sum _{x,y\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d\left(y\right)d(x,y)+2\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,v_1)\hfill \\ & & +\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)+2\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,v_1)+3\hfill \\ & =& \mathrm{Gut}\left(U_{n-1}\left(k\right)\right)+\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)+2\sum _{x\in V\left(H\right)\setminus \{w,v_1\}}d\left(x\right)d(x,v_1)+3\hfill \\ & =& \mathrm{Gut}\left(U_{n-1}\left(k\right)\right)+2(2\sum _{x\in V\left(C_k\right)\setminus \{v_k,v_1\}}d(x,v_1)+(n-k+1)\hfill \\ & & +2(n-k-1))+2n-1\hfill \\ & =& \mathrm{Gut}\left(U_{n-1}\left(k\right)\right)+4D_{C_k}\left(v_1\right)+8n-6k-7.\hfill \end{array}$$

We can deduce from above that

$$\mathrm{Gut}\left(U_n\left(k\right)\right)=\left\{\begin{array}{c}\frac{1}{2}\left(4n^2+(2k^2-4k+6)n-k^3-6k-8\right),\mathrm{if} k \mathrm{is} \mathrm{even};\hfill \\ \\ \frac{1}{2}\left(4n^2+(2k^2-4k+4)n-k^3-5k-8\right),\mathrm{if} k \mathrm{is} \mathrm{odd}.\hfill \end{array}\right.$$

□

Lemma 4.

Suppose that $m+1\le k\le 2m-2$. If $m\ge 5$ or $(m,k)=(4,6)$, then $\mathrm{Gut}\left(U_{2m}\left(k\right)\right)>16m^2-22m+7$.

Proof. 

If $(m,k)=(4,6)$, then it can be checked that $\mathrm{Gut}\left(U_{2m}\left(k\right)\right)=214>\mathrm{Gut}\left(U_{2m,m}\right)$ = 175. We discuss according to the parity of k for $k\ge 5$ next.

Case 1. If k is even, then $\mathrm{Gut}\left(U_{2m}\left(k\right)\right)=f\left(k\right)$, where

$$f\left(k\right)=\frac{1}{2}\left(16m^2+(4k^2-8k+12)m-k^3-6k-8\right).$$

It is easy to check that

$$f^{\prime }\left(k\right)=\frac{1}{2}\left((8k-8)m-3k^2-6\right),f^{\prime \prime }\left(k\right)=\frac{1}{2}\left(8m-6k\right).$$

Then $f^{\prime \prime }\left(k\right)$ is positive in $(m+1,\frac{4}{3}m)$, negative in $(\frac{4}{3}m,2m-2)$. Hence $f^{\prime }\left(k\right)$ is increasing in $(m+1,\frac{4}{3}m)$ and decreasing in $(\frac{4}{3}m,2m-2)$. Thus, $f^{\prime }\left(k\right)$ takes its minimal value at $k=m+1$ or $k=2m-2$.

• $f^{\prime }(m+1)=\frac{1}{2}(5m^2-6m-9)>0$ for $m\ge 5$.
• $f^{\prime }(2m-2)=2m^2-9>0$ for $m\ge 5$.

So we obtain that $f^{\prime }\left(k\right)>0$ for $m+1\le k\le 2m-2$, and therefore $f\left(k\right)\ge f(m+1)$.

It is easy to see that

$f(m+1)-(16m^2-22m+7)=\frac{1}{2}(m-1)(3m^2+16m+15)-(16m^2-22m+7)=\frac{1}{2}(3m^3-19m^2+43m-29)>0$ for $m\ge 5$.

Case 2. If k is odd, then $\mathrm{Gut}\left(U_{2m}\left(k\right)\right)=f\left(k\right)$, where

$$f\left(k\right)=\frac{1}{2}\left(16m^2+(4k^2-8k+8)m-k^3-5k-8\right).$$

It is easy to check that

$$f^{\prime }\left(k\right)=\frac{1}{2}\left((8k-8)m-3k^2-5\right),f^{\prime \prime }\left(k\right)=\frac{1}{2}\left(8m-6k\right).$$

Then $f^{\prime \prime }\left(k\right)$ is positive in $(m+1,\frac{4}{3}m)$, negative in $(\frac{4}{3}m,2m-2)$. Hence $f^{\prime }\left(k\right)$ is increasing in $(m+1,\frac{4}{3}m)$ and decreasing in $(\frac{4}{3}m,2m-2)$. Thus, $f^{\prime }\left(k\right)$ takes its minimal value at $k=m+1$ or $k=2m-2$.

• $f^{\prime }(m+1)=\frac{1}{2}(m-2)(5m+4)>0$ for $m\ge 5$.
• $f^{\prime }(2m-2)=\frac{1}{2}(4m^2-17)>0$ for $m\ge 5$.

So we obtain that $f^{\prime }\left(k\right)>0$ for $m+1\le k\le 2m-2$, and therefore $f\left(k\right)\ge f(m+1)$.

It is easy to see that

$f(m+1)-(16m^2-22m+7)=\frac{1}{2}(m+1)(3m^2+10m-14)-(16m^2-22m+7)=\frac{1}{2}{(m-2)}^2(3m-7)>0$ for $m\ge 5$.

Combining the above cases, we complete the proof. □

For integer $m\ge 3$, let ${\mathbb{U}}^{\prime }\left(m\right)$ be the set of graphs in $\mathbb{U}(2m,m)$ containing a pendant vertex whose neighbor is of degree two. Let ${\mathbb{U}}^{\prime \prime }\left(m\right)=\mathbb{U}(2m,m)\setminus U^{\prime }\left(m\right)$.

Recall that $H_8$ is the graph obtained by attaching three pendant vertices to three consecutive vertices of $C_5$. It is easy to see that $\mathrm{Gut}\left(H_8\right)=193>\mathrm{Gut}\left(U_{2m,m}\right)=175$ for $m=4$.

Lemma 5.

Let $G\in {\mathbb{U}}^{\prime \prime }\left(m\right)$ with $m\ge 4$. Then $\mathrm{Gut}\left(G\right)>16m^2-22m+7$.

Proof. 

If $G\cong H_8$, then the result follows easily. If $G\ne H_8$, then by Lemma 1, $G\in {\mathbb{U}}^{\prime \prime }\left(m\right)$ implies that $G\cong C_{2m}$ or G is a graph of maximum degree three obtained by attaching some pendant vertices to a cycle. If $G\cong C_{2m}$, $\mathrm{Gut}\left(C_{2m}\right)=4W\left(C_{2m}\right)=4m^3>16m^2-22m+7$.

Suppose that $G\ne C_{2m}$. Then G is a graph of maximum degree three obtained by attaching some pendant vertices to a cycle $C_k$, where $m\le k\le 2m-1$.

If $k=m$, then every vertex on the cycle has degree three, and therefore any vertex on the cycle is adjacent to a unique pendant vertex. A direct computation shows that:

If $m\ge 4$ is even, then $\mathrm{Gut}\left(G\right)=m(2m^2+4m-1)>16m^2-22m+7.$

If $m\ge 5$ is odd, then as above $\mathrm{Gut}\left(G\right)=m(2m^2+4m-3)>16m^2-22m+7.$

If $m+1\le k\le 2m-2$, then $m\ge 5$ or $(m,k)=(4,6)$ since $G\ne H_8$, by Lemma 4, for some $U_{2m}\left(k\right)$, we have $\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}\left(U_{2m}\left(k\right)\right)>16m^2-22m+7$.

If $k=2m-1$, then G is the graph obtained from $C_k$ by attaching a pendant vertex. By direct computations, we have $\mathrm{Gut}\left(G\right)=4m^3-2m^2+2m-1>16m^2-22m+7$ for $m\ge 4$.

In the following, if G is a graph in ${\mathbb{U}}^{\prime }\left(m\right)$ with a perfect matching M, then G contains a pendant vertex u whose neighbor v is of degree two in G, and assume w is the neighbor of v different from u. Obviously, $uv\in M$. Since $\left|M\right|=m$, we have $d_G\left(w\right)\le m+1$. □

By immediate calculations, we could verify the following lemma.

Lemma 6.

Among the graphs in $\mathbb{U}(6,3)$, $H_6$ is the unique graph with minimum Gutman index 81; and $U_{6,3}$ is the only graph with the second minimum Gutman index 85.

Lemma 7.

Let $G\in \mathbb{U}(8,4)$. Then $\mathrm{Gut}\left(G\right)\ge 175$ with equality if and only if $G\cong U_{8,4}$.

Proof. 

If $G\in {\mathbb{U}}^{\prime \prime }\left(4\right)$, then by Lemma 4, $\mathrm{Gut}\left(G\right)>175$. If $G\in {\mathbb{U}}^{\prime }\left(4\right)$, then $G-u-v\in \mathbb{U}(6,3)$. If $G-u-v\ne H_6$, then by Lemma 3

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u-v)-8d_G\left(w\right)+20n-30\ge 85-40+160-30=175,$$

with equality if and only if $G-u-v\cong U_{6,3}$, $d_G\left(w\right)=5$, $ecc\left(w\right)=2$, i.e., $G\cong U_{8,4}$.

If $G-u-v\cong H_6$, then $d_G\left(w\right)\le 4$, and by Lemma 3,

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}\left(H_6\right)-8d_G\left(w\right)+20n-30\ge 81-32+160-30=179>175.$$

The result follows. □

Lemma 8.

Let $G\in \mathbb{U}(10,5)$. Then $\mathrm{Gut}\left(G\right)\ge 297$ with equality if and only if $G\cong U_{10,5}$.

Proof. 

If $G\in {\mathbb{U}}^{\prime \prime }\left(5\right)$, then by Lemma 4, $\mathrm{Gut}\left(G\right)>297$. If $G\in {\mathbb{U}}^{\prime }\left(5\right)$. Then $G-u-v\in \mathbb{U}(8,4)$. By Lemma 3

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u-v)-8d_G\left(w\right)+20n-30\ge 175-48+200-30=297,$$

with equality if and only if $G-u-v\cong U_{8,4}$, $d_G\left(w\right)=6$, $ecc\left(w\right)=2$, i.e., $G\cong U_{10,5}$. □

In the rest of the paper, we are going to present the proofs of the main results described in Section 1.

Proof of Theorem 1.

The case $m=2$ is obvious since $\mathbb{U}(4,2)=\{C_4,U_{4,2}\}$, $\mathrm{Gut}\left(C_4\right)=32$, $\mathrm{Gut}\left(U_{4,2}\right)=27$. The cases $m=3$ and $m=4$ follow from Lemmas 6 and 7, respectively.

Suppose that $m\ge 5$. Let $g\left(m\right)=16m^2-22m+7$. We prove the result by induction on m. If $m=5$, then the result follows from Lemma 8. Suppose that $m\ge 6$ and the result holds for graphs in $\mathbb{U}(2m-2,m-1)$. Let $G\in \mathbb{U}(2m,m)$. If $G\in {\mathbb{U}}^{\prime \prime }\left(m\right)$, then G contains a pendant vertex u whose neighbor v is of degree two in G, and assume w is the neighbor of v different from u. By Lemma 4, $D^{\prime }\left(G\right)>g\left(m\right)$. If $G\in {\mathbb{U}}^{\prime }\left(m\right)$, then $G-u-v\in \mathbb{U}(2m-2,m-1)$, and thus by Lemma 3 and the induction hypothesis, it is easily seen that

$$\begin{array}{ccc}\hfill \mathrm{Gut}\left(G\right)& \ge & \mathrm{Gut}(G-u-v)-8d_G\left(w\right)+20n-30\hfill \\ & \ge & g(m-1)-8(m+1)+40m-30\hfill \\ & =& 16m^2-54m+45-8(m+1)+40m-30=g\left(m\right),\hfill \end{array}$$

with equality if and only if $G-u-v\cong U_{2(m-1),m-1}$, $d_G\left(w\right)=m+1$, $ecc\left(w\right)=2$, i.e., $G\cong U_{2m,m}$. □

Recall that $H_7$ is the graph obtained from $H_6$ by attaching one pendant vertex to a vertex of degree 3 in $H_6$.

Now, we can prove Theorem 2.

Proof of Theorem 2.

The case $(n,m)=(6,3)$ follows from Lemma 6. Suppose that $(n,m)\ne (6,3)$. Let $g(n,m)=2n^2+4mn-7n-8m+7$.

For $C_7$, we have $\mathrm{Gut}\left(C_7\right)=168>g(7,3)=116$. For $C_n$ with $n\ge 8$, we have either $n=2m$, bear in mind that $(n,m)\ne (6,3)$, $\mathrm{Gut}\left(C_n\right)=4W\left(C_n\right)=4m^3>g(n,m)=16m^2-22m+7;$ or $n=2m+1$, $\mathrm{Gut}\left(C_n\right)=4W\left(C_n\right)=4m^3+6m^2+2m>g(n,m)=16m^2-10m+2.$

If $G\ne C_n$ with $n>2m$, then by Lemma 2, there exists a pendant vertex x and a maximum matching M such that x is not M-saturated in G, and thus $G-x\in \mathbb{U}(n-1,m)$. Let y be the unique neighbor of x. Since M contains one edge incident with y, and there are $n-m$ edges of G outside M, we have $d_G\left(y\right)\le n-m+1$.

Case 1.$m=2$. The result for $n=4$ is obvious as in previous theorem. For $n=5$, it may be checked directly the five possibilities for G to obtain that $U_{5,2}$ has the minimum Gutman index 46. For $n\ge 6$, it is known in [23,24] that $U_{n,2}$ is the unique unicyclic graph on n vertices with minimum Gutman index.

Case 2.$m=3$. The result for $n=6$ is obvious as in previous lemma. If $n=7$, then $G-x\in \mathbb{U}(6,3)$. If $G-x\cong H_6$, then $d_G\left(y\right)\le 4$, and by Lemma 3,

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\ge 81-16+56-5=116,$$

with equalities if and only if $d_G\left(y\right)=4$ and $ecc\left(y\right)=2$, i.e., $G\cong H_7$.

If $G-x\ne H_6$, then by Lemma 3 we have

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\ge 85-20+56-5=116,$$

with equalities if and only if $G-x\cong U_{6,3}$. $d_G\left(y\right)=5$ and $ecc\left(y\right)=2$, i.e., $G\cong U_{7,3}$. Thus, for $n=7$, we have $D^{\prime }\left(G\right)\ge 116$ with equality if and only if $G\cong H_7$ or $U_{7,3}$.

For $n\ge 8$, we prove the result by induction on n. If $n=8$, then $G-x\in \mathbb{U}(7,3)$. By Lemma 3,

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\ge 116-24+64-5=151,$$

with equalities if and only if $G-x\cong U_{7,3}$, $d_G\left(y\right)=6$ and $ecc\left(y\right)=2$, i.e., $G\cong U_{8,3}$.

Suppose that $n\ge 9$ and the result holds for graphs in $\mathbb{U}(n-1,3)$. By Lemma 3 and the induction hypothesis,

$$\begin{array}{ccc}\hfill \mathrm{Gut}\left(G\right)& \ge & \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\hfill \\ & \ge & 2n^2+n-20-4(n-2)+8n-5\hfill \\ & =& 2n^2+5n-17,\hfill \end{array}$$

with equalities if and only if $G-x\cong U_{n-1,3}$, $d_G\left(y\right)=n-2$ and $ecc\left(y\right)=2$, i.e., $G\cong U_{n,3}$.

Case 3.$m=4$. The case $n=8$ follows from Lemma 7. For $n\ge 9$, we prove the result by induction on n. If $n=9$, then $G-x\in \mathbb{U}(8,4)$, and by Lemmas 7 and 3,

$$\mathrm{Gut}\left(G\right)\ge \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\ge 175-24+72-5=218,$$

with equalities if and only if $G-x\cong U_{8,4}$, $d_G\left(y\right)=6$ and $ecc\left(y\right)=2$, i.e., $G\cong U_{9,4}$.

Suppose that $n\ge 10$ and the result holds for graphs in $\mathbb{U}(n-1,4)$. By Lemma 3 and the induction hypothesis,

$$\begin{array}{ccc}\hfill \mathrm{Gut}\left(G\right)& \ge & \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\hfill \\ & \ge & 2n^2+5n-32-4(n-3)+8n-5=2n^2+9n-25,\hfill \end{array}$$

with equalities if and only if $G-x\cong U_{n-1,4}$, $d_G\left(y\right)=n-3$ and $ecc\left(y\right)=2$, i.e., $G\cong U_{n,4}$.

Case 4.$m\ge 5$. We prove the result by induction on n. If $n=2m$, then the result follows from Theorem 1. Suppose that $n>2m$ and the result holds for graphs in $\mathbb{U}(n-1,m)$. Let $G\in \mathbb{U}(n,m)$. By Lemma 3 and the induction hypothesis, it is easily seen that

$$\begin{array}{ccc}\hfill \mathrm{Gut}\left(G\right)& \ge & \mathrm{Gut}(G-u)-4d_G\left(v\right)+8n-5\hfill \\ & \ge & g(n-1,m)-4(n-m+1)+8n-5\hfill \\ & =& 2n^2+4mn-11n-12m+16-4(n-m+1)+8n-5=g(n,m),\hfill \end{array}$$

with equality if and only if $G-x\cong U_{n-1,m}$, $d_G\left(y\right)=n-m+1$, $ecc\left(y\right)=2$, i.e., $G\cong U_{n,m}$.

Combining the above cases, the result follows. □

3. Conclusion Remark

Let $\mathbb{U}(n,m)$ be the unicyclic graph on n vertices with matching number m. In this paper, we first consider the particular case of $\mathbb{U}(2m,m)$. We completely determine the graph minimizing the Gutman index among $\mathbb{U}(2m,m)$ by induction on m. The key of our idea is that, if G minimizing the Gutman index among $\mathbb{U}(2m,m)$ then there exist two vertices $u,v$ such that $G-u-v$ minimizing the Gutman index among $\mathbb{U}(2m,m)$. For the general case of $\mathbb{U}(n,m)$, we could make inductive on n since the first step of $n=2m$ was already solved. It seems that our methods are also useful for general graphs. Let $\mathcal{G}(n,m)$ be the set of connected graphs on n vertices with matching number m. We end up this paper by the following problem.

Problem 1.

Find the graph minimizing the Gutman index among $\mathcal{G}(n,m)$.