On symmetric division deg index of unicyclic graphs and bicyclic graphs with given matching number

1.   Introduction

As a numerical parameter of molecular structure, topological molecular descriptors play an important role in chemistry, pharmacology and materials science, etc. (see ^[1,2,3]). Symmetric division deg ($SDD$ for short) index is one of the 148 discrete Adriatic indices that showed good predictive abilities on the testing sets provided by International Academy of Mathematical Chemistry (IAMC) ^[4]. This graph invariant has a good correlation with the total surface area of polychlorobiphenyls ^[4], and its extremal graphs which have a particularly elegant and simple structure are obtained with the help of MathChem ^[5]. Let us write the definition of $SDD$ index again, that is

where $d_{G}(u)$ denotes the degree of vertex $u$ in $G$. Recently, Furtula et al. ^[6] found that $SDD$ index is an applicable and viable topological index, whose predictive capability is better than that of some popular topological indices, such as the famous geometric-arithmetic index and the second Zagreb index. Gupta et al. ^[7] determined some upper and lower bounds of $SDD$ index on some classes of graphs and characterized the corresponding extremal graphs. For other recent mathematical investigations, the readers can refer ^{[8,9,10,11,12,13,14,15,16]}.

At present, studying the behavior of topological indices is an essential subject. $SDD$ index has been studied extensively since it was proved to be an applicable and viable molecular descriptor in 2018. Furthermore, unicyclic graphs and bicyclic graphs are two kinds of important graphs in mathematical chemistry because they can be seen as the molecular graphs of some chemical compounds. There are many papers on topological indices of unicyclic graphs and bicyclic graphs. Recent results can be referred to ^[17,18,19] et al. So we study the extremal values of $SDD$ indices on unicyclic graphs and bicyclic graphs with given matching number and find the corresponding extremal graphs. Our results may be used to detect the chemical compounds that may have desirable properties. Namely, if one can find some properties well-correlated with this descriptor ($SDD$ index has a good correlation with the total surface area of polychlorobiphenyls), the extremal graphs should correspond to molecules with minimum or maximum value of that property.

We only deal with connected graphs without multiple edges and loops. We use $G = (V(G), E(G))$ to denote the graph with vertex set $V(G)$ and edge set $E(G)$. Let $N_{G}(x)$ be the set of all neighbours of $x\in V(G)$ in $G$, and $d_{G}(x) = |N_{G}(x)|$. If $d_{G}(x) = 1$, we call $x$ is a pendant vertex, and denoted by $PV(G)$ the set of all pendant vertices in $G$. We denote the distance between vertices $u$ and $v$ of $G$ by $d_{G}(u, v)$. Let $G-xy$ and $G-x$ be the graph obtained from $G$ by deleting the edge $xy \in E(G)$ and the vertex $x \in V(G)$, respectively. Similarly, $G+uv$ is the graph obtained from $G$ by adding an edge $uv \notin E(G)$, where $u, v\in V (G)$. Unicyclic graphs $U$ and bicyclic graphs $B$ are connected graphs satisfying $|E(U)| = |V(U)|$ and $|E(B)| = |V(B)|+1$, respectively. As usual, let's denote the path, the cycle and the star on $n$ vertices by $P_{n}$, $C_{n}$ and $S_{n}$, respectively.

There are two categories of bases of bicyclic graphs, as described here. Denoted by $\infty(p, l, q)$ the graph obtained from two vertex-disjoint cycles $C_{p}$ and $C_{q}$ by connecting one vertex $u^{*}$ of $C_{p}$ and one vertex $v^{*}$ of $C_{q}$ with a path $P_{l+1} = u^{*}\cdots v^{*}$ of length $l$ (if $l = 0$, identifying $u^{*}$ with $v^{*}$), as depicted in Figure 1. Denoted by $\theta(a, b, c)$ the union of three internally disjoint paths $P_{a+1}$, $P_{b+1}$, $P_{c+1}$ of length $a, b, c$ ($a, b, c\geq 1$ and at most one of them is 1) respectively with common end vertices $u^{*}$ and $v^{*}$, as depicted in Figure 1. Notice that any bicyclic graph is obtained from a $\theta(a, b, c)$ or an $\infty(p, l, q)$ by attaching trees to some of its vertices. The bicyclic graphs containing $\infty(p, l, q)$ and $\theta(r, s, t)$ as its base are called $\infty$-graph and $\theta$-graph, respectively.

A subset $M\subseteq E(G)$ is called a matching of $G$ if no pair of edges in $M$ share a common vertex. The matching number a graph $G$ is the maximum cardinality of a matching in $G$. If vertex $x\in V(G)$ is incident with some edges of $M$, where $M$ is a matching of $G$, then $x$ is said to be $M$-saturated. $M$ is called a perfect matching if each vertex of $G$ is $M$-saturated. We can refer ^[20] for other terminologies and notations.

2.   Preliminaries

Let $S(x, y) = \frac{x}{y}+\frac{y}{x}$, where $x, y\geq 1$. One can easily get the Lemmas 2.1 and 2.2.

Lemma 2.1. Let $h_{t}(x) = S(x, t+1)-S(x, t) = \frac{x}{t+1}-\frac{x}{t}+\frac{1}{x}$, where $x, t\geq 1$. Then $h_{t}(x)$ is decreasing for $x$.

Lemma 2.2. Let $\varphi_{1}(t) = t+\frac{1}{t+1}-\frac{1}{t+2}$ and $\varphi_{2}(t) = t+\frac{1}{t+2}-\frac{1}{t+3}$, where $t\geq 1$. Then $\varphi_{1}(t)$ and $\varphi_{2}(t)$ are increasing for $t$.

Lemma 2.3. Let $\psi(m) = \frac{m^{2}}{2}-\frac{4}{3}m-\frac{1}{m+1}$. Then $\psi(m) > 0$ for $m\geq 3$.

Proof. Notice that for $m\geq 3$,

So $\psi(m)\geq \psi(3) = \frac{1}{4} > 0$.

Lemma 2.4. Let $l(t, r) = \frac{3}{2}t+\frac{r-1}{t-1}-\frac{r}{t} = \frac{3}{2}t+\frac{r-t}{t(t-1)}$, where $r, t\geq 2$ and $r < t$. Then $l(t, r)$ is increasing for $t$ and $r$, respectively.

Proof. It is evident that $l(t, r)$ is increasing for $r$. Furthermore, since

then $l(t, r)$ is increasing for $t$.

Lemma 2.5. ^[14] Among the set of $n$-vertex $(n\geq3)$ unicyclic graphs, the cycle $C_{n}$ is the unique graph with the minimum $SDD$ index.

3.   $\boldsymbol{SDD}$ index of unicyclic graphs with given matching number

For integers $m\geq 2$, denoted by $\boldsymbol{\mathscr{U}}_{n, m}$ the set of $n$-vertex unicyclic graphs with matching number $m$.

Let $\boldsymbol{U}^{*}_{n, m}$ be the unicyclic graphs on $n$ vertices arisen from $C_{3}$ by attaching $n-2m+1$ pendant edges and $m-2$ paths of length 2 to its one vertex, as depicted in Figure 2. Let $SDD(\boldsymbol{U}^{*}_{n, m}) = f(n, m)$, where

Lemma 3.1. ^[21] Let $U\in \boldsymbol{\mathscr{U}}_{2m, m}$ and $T$ be a tree in $U$ attached to a root $r$, where $m\geq 3$. If $y\in V(T)$ is a vertex furthest from the root $r$ with $d_{U}(y, r)\geq 2$, then $y$ is a pendant vertex and adjacent to a vertex $x$ of degree 2.

Lemma 3.2. ^[22] Let $U\in \boldsymbol{\mathscr{U}}_{2m, m}$. If $PV(U)\neq \emptyset$, then for any vertex $x\in V(G)$, $\mid N_{U}(x)\cap PV(U)\mid \leq1$.

Lemma 3.3. ^[23] Let $U\in \boldsymbol{\mathscr{U}}_{n, m}$ $(n > 2m)$ and $U\ncong C_{n}$. Then there exist an $m$-matching $M$ and a pendant vertex $y$ such that $M$ does not saturate $y$.

Theorem 3.4. Let $U\in \boldsymbol{\mathscr{U}}_{2m, m}$, where $m\geq 2$. Then

with equality if and only if $U\cong \boldsymbol{U}^{*}_{2m, m}$.

Proof. By induction on $m$. If $m = 2$, then $U\cong \boldsymbol{U}^{*}_{4, 2}$ or $U\cong C_{4}$. Notice that $SDD(C_{4}) = 8 < SDD(\boldsymbol{U}^{*}_{4, 2}) = f(4, 2) = \frac{29}{3}$. Thus for $m = 2$, the theorem is true.

We assume that $m\geq3$ and the result holds for all unicyclic graphs on fewer than $2m$ vertices with a perfect matching. Suppose $M$ is a perfect matching of $U$. If $U\cong C_{2m}$, by Lemma 2.5, it follows that $SDD(C_{2m}) < SDD(\boldsymbol{U}^{*}_{2m, m}) = f(2m, m)$. So we assume that $U\ncong C_{2m}$ in the following proof. This implies that $PV(U)\neq\emptyset$.

Let $y\in PV(U)$, then $U$ contains a tree $T_{r}$ attached on a root $r\in V(C)$ such that $y\in V(T_{r})$, where $C$ is the cycle of $U$. Let $d_{T_{r}}(r, z) = \max \{d_{T_{r}}(r, y)| y\in V(T_{r})\}$ and $\boldsymbol{\mathscr{T}}_{U}$ be the set of all pendant trees in $U$. We discuss in three cases.

Case 1. $\max \{d_{T_{r}}(r, z)|T_{r}\in \boldsymbol{\mathscr{T}}_{U}\} = 1$.

In view of Lemma 3.2, then $U$ is obtained from a cycle, say $C_{s} = x_{1}x_{2}\cdots x_{s}x_{1}$, by adding a pendant edge to some vertices on $C_{s}$. If just one pendant edge is attached to every vertex of $C_{s}$, then $SDD(U) = m(S(1, 3)+S(3, 3)) = \frac{16}{3}m$. By Lemma 2.3, for $m\geq 3$, $SDD(\boldsymbol{U}^{*}_{2m, m})-SDD(U) = f(2m, m)-\frac{16}{3}m = \frac{m^{2}}{2}-\frac{4}{3}m-\frac{1}{m+1} > 0$.

Otherwise, there exists at least one vertex, say $x$, with $d_{U}(x) = 2$ on $C_{s}$. Since $U\ncong C_{2m}$, there exist $i\in\{1, 2, \cdots, s\}$ such that $d_{U}(x_{i}) = 3$ and $d_{U}(x_{i+1}) = 2$, where $x_{s+1} = x_{1}$. Assume without loss of generality that $d_{U}(x_{2}) = 3$ and $d_{U}(x_{3}) = 2$. Let $y_{2}$ be the pendant vertex adjacent to $x_{2}$. Since $U\in \boldsymbol{\mathscr{U}}_{2m, m}$, it can be seen that a two-degree vertex can not be adjacent to two three-degree vertices. Thus $d_{U}(x_{4}) = 2$ and $x_{3}x_{4}\in M$. Let $U' = U-\{y_{2}, x_{3}\}+x_{2}x_{4}$, then $U'\in \boldsymbol{\mathscr{U}}_{2m-2, m-1}$. By the definition of $SDD$ index, induction hypothesis and Lemma 2.1, it follows that

since $f(2m, m)-f(2m-2, m-1)-\frac{17}{3} = m-\frac{13}{6}+\frac{1}{m}-\frac{1}{m+1} > 0$ for $m\geq 3$.

Case 2. $U$ contains a pendant tree $T_{r}\in \boldsymbol{\mathscr{T}}_{U}$ such that $d_{T_{r}}(r, z) = 2$.

Since $z\in PV(U)$, then denote $N_{U}(z) = \{u\}$, by Lemma 3.1, we have $d_{U}(u) = 2$. Let $N_{U}(u) = \{r, z\}$ and $N_{U}(r) = \{u, x_{1}, x_{2}, v_{1}, v_{2}, \cdots, v_{t}\}$, where $x_{i}\in V(C)$, $d_{U}(x_{i})\geq 2$ ($i = 1, 2$).

Subcase 2.1. There is $v_{i}\in PV(U)$, where $v_{i}\in \{v_{1}, v_{2}, \cdots, v_{t}\}$.

Assume without loss of generality that $v_{1}\in PV(U)$, then $v_{1}r\in M$. By Lemma 3.2, $(N_{U}(r)\setminus \{v_{1}\})\cap PV(U) = \emptyset$. Then $d_{U}(v_{i})\geq 2$, $i = 2, 3, \cdots, t$. Since $d_{T_{r}}(r, z) = \max \{d_{T_{r}}(r, y)| y\in V(T_{r})\} = 2$, combined with Lemma 3.1, it follows that $d_{U}(v_{i}) = 2$ and $N_{U}(v_{i})\setminus \{r\} = \{z_{i}\}\in PV(U)$, where $i = 2, 3, \cdots, t$. Let $U' = U-z-u$. Then $U'\in \boldsymbol{\mathscr{U}}_{2m-2, m-1}$. By the definition of $SDD$ index, induction hypothesis and Lemmas 2.1, 2.2, we have

since $t\leq m-2$. The equalities above hold only if $SDD(U')$ $= f(2m-2, m-1)$, $V(U) = \{x_{1}, x_{2}, r, v_{1}, u, z\}\cup \{z_{2}, z_{3}, \cdots, z_{t}\}\cup\{v_{2}, v_{3}, \cdots, v_{t}\}$ and $d_{U}(x_{1}) = d_{U}(x_{2}) = 2$, which implies that $U'\cong \boldsymbol{U}^{*}_{2m-2, m-1}$, and $U\cong \boldsymbol{U}^{*}_{2m, m}$.

Subcase 2.2. For all $v_{i}\in N_{U}(r)\setminus\{u, x_{1}, x_{2}\}$ ($i = 1, 2, \cdots, t$), $v_{i}\notin PV(U)$.

Then $d_{U}(v_{i}) = 2$, $N_{U}(v_{i})\setminus\{r\} = \{z_{i}\}\subset PV(U)$, where $v_{i}z_{i}\in M$, $i = 1, 2, \cdots, t$. Since $U\in \boldsymbol{\mathscr{U}}_{2m, m}$, there exists a vertex $x_{j}\in \{x_{1}, x_{2}\}$ such that $x_{j}r\in M$. Let $U'' = U-z-u$. Then $U''\in \boldsymbol{\mathscr{U}}_{2m-2, m-1}$. By the definition of $SDD$ index, induction hypothesis and Lemma 2.1, it follows that

since $t < m-2$ and $f(2m, m)-f(2m-2, m-1)-m-3 = \frac{1}{m}-\frac{1}{m+1}+\frac{1}{2} > 0$ for $m\geq 3$.

Case 3. For all $T_{r}\in \boldsymbol{\mathscr{T}}_{U}$, $d_{T_{r}}(r, z)\neq2$ and $\max \{d_{T_{r}}(r, z)|T_{r}\in \boldsymbol{\mathscr{T}}_{U}\}\geq 3$.

Similar to Case 2, as $z\in PV(U)$, denote $N_{U}(z) = \{u\}$, by Lemma 3.1, $d_{U}(u) = 2$. $N_{U}(u) = \{v, z\}$ and $N_{U}(v) = \{u, w, v_{1}, v_{2}, \cdots, v_{t}\}$ (maybe $w = r$), then $d_{U}(w)\geq2$.

Subcase 3.1. There exists $v_{i}\in PV(U)$, where $v_{i}\in \{v_{1}, v_{2}, \cdots, v_{t}\}$.

Assume without loss of generality that $v_{1}\in PV(U)$, then $v_{1}v\in M$. Similar to Subcase 2.1, we have $d_{U}(v_{i}) = 2$ and $N_{U}(v_{i})\setminus \{v\} = \{z_{i}\}\subset PV(U)$, where $i = 2, 3, \cdots, t$. Let $U' = U-z-u$. Then $U'\in \boldsymbol{\mathscr{U}}_{2m-2, m-1}$. By the definition of $SDD$ index, induction hypothesis and Lemmas 2.1, 2.2, we have

since $t < m-2$ and $f(2m, m)-f(2m-2, m-1)-m-\frac{5}{2}-\frac{1}{m-1}+\frac{1}{m} = 1+(\frac{1}{m}-\frac{1}{m+1})-\frac{1}{m-1}+\frac{1}{m} > 1-\frac{1}{m-1}+\frac{1}{m} > 0$ for $m\geq 3$.

Subcase 3.2. For all $v_{i}\in N_{U}(v)\setminus\{u, w\}$ ($i = 1, 2, \cdots, t$), $v_{i}\notin PV(U)$.

Similar to Subcase 2.2, we have $d_{U}(v_{i}) = 2$, $N_{U}(v_{i})\setminus\{v\} = \{z_{i}\}\subset PV(U)$, where $v_{i}z_{i}\in M$, $i = 1, 2, \cdots, t$. Since $U\in \boldsymbol{\mathscr{U}}_{2m, m}$, then $vw\in M$. Let $U'' = U-z-u$. Then $U''\in \boldsymbol{\mathscr{U}}_{2m-2, m-1}$. By the definition of $SDD$ index, induction hypothesis and Lemma 2.1, we have

since $t < m-2$ and $f(2m, m)-f(2m-2, m-1)-m-2 = \frac{3}{2}+\frac{1}{m}-\frac{1}{m-1} > 0$ for $m\geq 3$.

Theorem 3.5. Suppose $U\in \boldsymbol{\mathscr{U}}_{n, m}$, where $m\geq 2$. Then

with equality if and only if $U\cong \boldsymbol{U}^{*}_{n, m}$.

Proof. By induction on $n$. If $n = 2m$, by Theorem 3.4, the result holds. Now suppose that $n > 2m$. If $U\cong C_{n}$, it can be seen that $n = 2m+1$. By Lemma 2.5, it follows that $SDD(C_{2m+1}) < SDD(\boldsymbol{U}^{*}_{2m+1, m})$. The theorem holds. Thus we suppose that $U\ncong C_{n}$ in the following proof. By Lemma 3.3, it follows that there is a pendant vertex $y$ and an $m$-matching $M$ such that $y$ is not $M$-saturated. Let $xy\in E(U)$ and $d_{U}(x) = t$. Let $N_{U}(x)\cap PV(U) = \{y_{1}, y_{2}, \cdots, y_{r-1}, y_{r} = y\}$ and $N_{U}(x)\setminus PV(U) = \{u_{1}, u_{2}, \cdots, u_{t-r}\}$. Then $d_{U}(u_{i})\geq 2$ for each $i = 1, 2, \cdots, t-r$. Furthermore, since $U$ is a unicyclic graph and there exist at least $m-2$ $M$-saturated vertices in $V(U)\setminus\{x, y_{1}, y_{2}, \cdots, y_{r-1}, y_{r}, u_{1}, u_{2}, \cdots, u_{t-r}\}$, then $n = |V(U)|\geq t+1+m-2$, that is $t\leq n-m+1$. Let $U' = U-y$. Then $U'\in \boldsymbol{\mathscr{U}}_{n-1, m}$. We discuss in two cases.

Case 1. $r = 1$.

Now, $y = y_{1}$. By the induction hypothesis and Lemma 2.1, for $n > 2m$, it follows that

Case 2. $r\geq 2$.

Notice that there exist at least $r-1$ vertices which are not $M$-saturated, then $n-(r-1)\geq 2m$, that is $r\leq n-2m+1$. By the induction hypothesis and Lemmas 2.1, 2.4, it follows that

With the equalities hold only if $SDD(U') = f(n-1, m)$, $t = n-m+1$, $r = n-2m+1$ and $d_{U}(u_{j}) = 2$ for $j = 1, 2, \cdots, t-r$, which implies that $U'\cong \boldsymbol{U}^{*}_{n-1, m}$, and $U\cong \boldsymbol{U}^{*}_{n, m}$.

4.   $\boldsymbol{SDD}$ index of bicyclic graphs with given matching number

For integers $m\geq 3$, denoted by $\boldsymbol{\mathscr{B}}_{n, m}$ the set of $n$-vertex bicyclic graphs with matching number $m$.

Let $\boldsymbol{B}^{*}_{n, m}$ be the bicyclic graphs on $n$ vertices arisen from $\infty(3, 0, 3)$ by attaching $n-2m+1$ pendant edges and $m-3$ paths of length 2 to the vertex of degree 4 in $\infty(3, 0, 3)$, as depicted in Figure 3. Let $SDD(\boldsymbol{B}^{*}_{n, m}) = g(n, m)$, where

Lemma 4.1. ^[24] Let $B\in \boldsymbol{\mathscr{B}}_{2m, m}$ and $T$ be a tree in $B$ attached to a root $r$, where $m\geq 3$. If $y\in V(T)$ is a vertex furthest from the root $r$ with $d_{B}(y, r)\geq 2$, then $y$ is a pendant vertex and adjacent to a vertex $x$ of degree 2.

Lemma 4.2. ^[25] Let $B\in \boldsymbol{\mathscr{B}}_{2m, m}$. If $PV(B)\neq \emptyset$, then for any vertex $x\in V(B)$, $\mid N_{B}(x)\cap PV(B)\mid \leq1$.

Lemma 4.3. ^[24] Let $B\in \boldsymbol{\mathscr{B}}_{n, m}$ $(n > 2m)$ and $B$ has at least one pendant vertex. Then there is an $m$-matching $M$ and a pendant vertex $y$ such that $M$ does not saturate $y$.

Theorem 4.4. Let $B\in \boldsymbol{\mathscr{B}}_{2m, m}$, where $m\geq 3$. Then

with equality if and only if $B\cong \boldsymbol{B}^{*}_{2m, m}$.

Proof. If $PV(B) = \emptyset$, $B$ belongs to the type of $\infty(p, l, q)$ or $\theta(a, b, c)$ (see Figure 1). It is easy to check that for $m\geq 3$, $SDD(\infty(p, l, q)) = SDD(\theta(a, b, c)) = 4m+3 < g(2m, m)$ ($l\neq 0$) when $u^{*}v^{*}\notin B$, $SDD(\infty(p, l, q)) = SDD(\theta(a, b, c)) = 4m+\frac{8}{3} < g(2m, m)$ ($l\neq 0$) when $u^{*}v^{*}\in B$ and $SDD(\infty(p, 0, q)) = 4m+4 < g(2m, m)$. So we suppose that $PV(B)\neq\emptyset$ in the following proof.

By induction on $m$. If $m = 3$, then $B\in \{B_{1}, B_{2}, \cdots, B_{7}\}$, where $B_{1}, B_{2}, \cdots, B_{7}$ are depicted in Figure 4. By direct calculation, $SDD(B_{i}) < SDD(B_{1}) = SDD(\boldsymbol{B}^{*}_{6, 3}) = g(6, 3)$, where $i = 2, \cdots, 7$. Thus for $m = 3$, the theorem is true.

We assume that $m\geq 4$ and the result holds for all bicyclic graphs on fewer than $2m$ vertices with a perfect matching. Suppose $M$ is a perfect matching of $B$. For $y\in PV(B)$, there exists a tree $T_{r}$ attached on a root $r\in V(\theta(a, b, c))$ or $r\in V(\infty(p, l, q)$ in $B$ such that $y\in V(T_{r})$, where $T_{r}$ is a pendant tree in $B$. Let $d_{T_{r}}(r, z) = \max \{d_{T_{r}}(r, y)| y\in V(T_{r})\}$ and $\boldsymbol{\mathscr{T}}_{B}$ be the set of all pendant trees in $B$. We discuss in three cases.

Case 1. $\max \{d_{T_{r}}(r, z)|T_{r}\in \boldsymbol{\mathscr{T}}_{B}\} = 1$.

Now, $B$ is a graph arisen from $\infty(p, l, q)$ or $\theta(a, b, c)$ by attaching some pendant edges to its some vertices. In view of Lemma 4.2, it follows that every vertex of $\infty(p, l, q)$ or $\theta(a, b, c)$ is attached by at most one pendant edge.

Subcase 1.1. For any $w\in V(B)$, $d_{B}(w)\neq 2$.

Since $B$ has a perfect matching, then $B\in\{B_{m}^{i}|i = 1, 2, \cdots, 7\}$, where $B_{m}^{i}$ $(i = 1, 2, \cdots, 7)$ are depicted in Figure 5. It is not difficult to get that $SDD(B_{m}^{1}) = \frac{16}{3}m+\frac{2}{3}$ ($m\geq 3$), $SDD(B_{m}^{3}) = \frac{16}{3}m+\frac{2}{3}$ ($m\geq 5$), $SDD(B_{m}^{2}) = \frac{16}{3}m+\frac{25}{6}$ ($m\geq 4$), $SDD(B_{m}^{4}) = \frac{16}{3}m+\frac{25}{6}$ ($m\geq 6$), $SDD(B_{m}^{5}) = \frac{16}{3}m+\frac{74}{15}$ ($m\geq 5$), $SDD(B_{m}^{6}) = \frac{16}{3}m+\frac{13}{3}$ ($m\geq 5$) and $SDD(B_{m}^{7}) = \frac{16}{3}m+\frac{13}{3}$ ($m\geq 7$). One can easily check that $SDD(\boldsymbol{B}^{*}_{2m, m}) = \frac{m^{2}}{2}+5m-\frac{1}{m+2}+\frac{3}{2} > SDD(B_{m}^{i})$, where $i = 1, 2, \cdots, 7$.

Subcase 1.2. $B$ contains one vertex $w$ with $d_{B}(w) = 2$.

Subsubcase 1.2.1. $w$ belongs to the vertices in one of the cycles of $B$.

Denote $N_{B}(w) = \{w_{1}, w_{2}\}$. Since $B\in \boldsymbol{\mathscr{B}}_{2m, m}$, then $ww_{1}\notin M$ or $ww_{2}\notin M$. Suppose without loss of generality that $ww_{1}\notin M$. Let $d_{B}(w_{1}) = t$, $N_{B}(w_{1})\setminus\{w\} = \{u_{1}, u_{2}, \cdots, u_{t-1}\}$. Since $B\in \boldsymbol{\mathscr{B}}_{2m, m}$, then $2\leq t\leq5$, $2\leq d_{B}(w_{2})\leq 5$ and $d_{B}(u_{i})\geq 1$, where $i = 1, 2, \cdots, t-1$. In view of Lemma 4.2, there exists at most one vertex of $\{u_{1}, u_{2}, \cdots, u_{t-1}\}$ with degree 1. Let $U' = B-ww_{1}$. Obviously, $U'\in \boldsymbol{\mathscr{U}}_{2m, m}$. By Theorem 3.4 and Lemmas 2.1, 2.2, for $2\leq t\leq5$ and $m\geq4$, it follows that

Subsubcase 1.2.2. $w$ lie in the path of a $\infty$-graph.

Now $B$ contains an edge $uv$ which belongs to a cycle such that $d_{B}(u) = d_{B}(v) = 3$. Denote $N_{B}(u) = \{v, u_{1}, u_{2}\}$ and $N_{B}(v) = \{u, v_{1}, v_{2}\}$. Assume without loss of generality that $d_{B}(u_{1}) = d_{B}(v_{1}) = 1$ and $3\leq d_{B}(u_{2}), d_{B}(v_{2})\leq 4$. Let $U'' = B-uv$. Then $U''\in \boldsymbol{\mathscr{U}}_{2m, m}$. By Theorem 3.4 and Lemma 2.1, it follows that

Case 2. There is a pendant tree $T_{r}\in \boldsymbol{\mathscr{T}}_{B}$ such that $d_{T_{r}}(r, z) = 2$.

Since $z\in PV(B)$, let $N_{B}(z) = \{u\}$, by Lemma 4.1, we have $d_{B}(u) = 2$. Let $N_{B}(u) = \{r, z\}$, $N_{B}(r) = \{u, x_{1}, x_{2}, \cdots, x_{s}, v_{1}, v_{2}, \cdots, v_{t}\}$, where $x_{i}$ belongs to the vertices of the cycles in $B$ and $d_{B}(x_{i})\geq 2$ $(i = 1, 2, \cdots, s$ and $s = 2, 3$ or $4)$.

Subcase 2.1. $PV(B)\cap N_{B}(r)\neq\emptyset$.

Suppose without loss of generality that $v_{1}\in PV(B)$, then $v_{1}r\in M$. By Lemma 4.2, $(N_{B}(r)\setminus\{v_{1}\})\cap PV(B) = \emptyset$. Then $d_{B}(v_{j})\geq 2$ for $2\leq j\leq t$. Since $d_{T_{r}}(r, z) = \max \{d_{T_{r}}(r, y)| y\in V(T_{r})\} = 2$, combine with Lemma 4.2, we have $d_{B}(v_{j}) = 2$ and $(N_{B}(v_{j})\setminus\{r\}) = \{z_{j}\}\in PV(B)$, where $2\leq j\leq t$. Let $B' = B-z-u$, then $B'\in \boldsymbol{\mathscr{B}}_{2m-2, m-1}$. By Lemmas 2.1, 2.2 and induction hypothesis, it follows that

since $S(t+s+1, k)-S(t+s, k)$ ($k = 1, 2$), $S(t+s+1, 2)$ is increasing for $s$ and $t\leq m-3$. With the equalities only if $V(B)\! = \!\{x_{1}, \cdots, x_{4}, r, v_{1}, u, z\}\cup \{v_{2}, \cdots, v_{t}, z_{2}, \cdots, z_{t}\}$, $s = 4$, $d_{B}(x_{1}) = \cdots = d_{B}(x_{4}) = 2$ and $SDD(B') = g(2m-2, m-1)$, which implies that $B'\cong \boldsymbol{B}^{*}_{2m-2, m-1}$ and $B\cong \boldsymbol{B}^{*}_{2m, m}$.

Subcase 2.2. $PV(B)\cap N_{B}(r) = \emptyset$.

Now we can see that $d_{B}(v_{j})\geq 2$, $(N_{B}(v_{j})\setminus\{r\}) = \{z_{j}\}\in PV(B)$, where $1\leq j\leq t$ and $v_{j}z_{j}\in M$. Since $B\in \boldsymbol{\mathscr{B}}_{2m, m}$, then $B$ contains one vertex $x_{j}\in N_{B}(r)$ and $x_{j}$ also belongs to the vertices of the cycles in $B$ such that $rx_{j}\in M$. Let $B' = B-z-u$, then $B'\in \boldsymbol{\mathscr{B}}_{2m-2, m-1}$. By Lemma 2.1 and induction hypothesis, it follows that

since $t < m-3$ and $g(2m, m)-g(2m-2, m-1)-m-4 = \frac{1}{2}+\frac{1}{m+1}-\frac{1}{m+2} > 0$ for $m\geq 4$.

Case 3. For all $T_{r}\in \boldsymbol{\mathscr{T}}_{B}$, $d_{T_{r}}(r, z)\neq2$ and $\max \{d_{T_{r}}(r, z)|T_{r}\in \boldsymbol{\mathscr{T}}_{B}\}\geq 3$.

Similar to Case 2, as $z\in PV(B)$, denote $N_{B}(z) = \{u\}$, by Lemma 4.1, $d_{B}(u) = 2$. Denote $N_{B}(u) = \{v, z\}$ and $N_{B}(v) = \{u, w, v_{1}, v_{2}, \cdots, v_{t}\}$ (maybe $w = r$), then $d_{B}(w)\geq2$.

Subcase 3.1. $N_{B}(v)\cap PV(B)\neq\emptyset$.

Assume without loss of generality that $v_{1}\in PV(U)$, then $v_{1}v\in M$. Similar to Subcase 2.1, we have $d_{B}(v_{i}) = 2$ and $N_{B}(v_{i})\setminus \{v\} = \{z_{i}\}\in PV(B)$, where $i = 2, 3, \cdots, t$. Let $B' = B-z-u$. Then $B'\in \boldsymbol{\mathscr{B}}_{2m-2, m-1}$. By Lemmas 2.1, 2.2 and induction hypothesis, it follows that

since $t < m-3$ and $g(2m, m)-g(2m-2, m-1)-m-\frac{3}{2}+\frac{1}{m-1}-\frac{1}{m-2} = 3+\frac{1}{m+1}-\frac{1}{m+2}+\frac{1}{m-1}-\frac{1}{m-2} > 3-\frac{1}{(m-1)(m-2)} > 0$ for $m\geq 4$.

Subcase 3.2. $N_{B}(v)\cap PV(B) = \emptyset$.

Similar to Subcase 2.2, we have $d_{B}(v_{i}) = 2$, $N_{B}(v_{i})\setminus\{v\} = \{z_{i}\}\in PV(B)$, where $v_{i}z_{i}\in M$, $i = 1, 2, \cdots, t$. Since $B\in \boldsymbol{\mathscr{B}}_{2m, m}$, then $vw\in M$. Let $B' = B-z-u$. Then $B'\in \boldsymbol{\mathscr{B}}_{2(m-1), m-1}$. By induction hypothesis and Lemma 2.1, we have

since $t < m-3$ and $g(2m, m)-g(2m-2, m-1)-m-1 = \frac{7}{2}+\frac{1}{m+1}-\frac{1}{m+2} > 0$.

Theorem 4.5. Let $B\in \boldsymbol{\mathscr{B}}_{n, m}$, where $m\geq 3$. Then

with equality if and only if $B\cong \boldsymbol{B}^{*}_{n, m}$.

Proof. By induction on $n$. If $n = 2m$, by Theorem 4.4, the result holds. Now suppose that $n > 2m$. If $PV(B) = \emptyset$, $B$ belongs to the type of $\infty(p, l, q)$ or $\theta(a, b, c)$ and $n = 2m+1$, then $p+l+q-1 = n = 2m+1$ and $a+b+c-1 = n = 2m+1$. For $p+l+q-1, a+b+c-1 = 2m+1$, one can easily check that $\max\{SDD(\infty(p, l, q)) (l\neq0), SDD(\theta(a, b, c)), SDD(\infty(p, 0, q))\}\! = \!SDD(\!\infty(p, 0, q)\!)$ and $SDD(\infty(p, 0, q)) = 4m+6 < SDD(\boldsymbol{B}^{*}_{2m+1, m}) = g(2m+1, m) = \frac{m^{2}}{2}+\frac{13m}{2}+5+\frac{m+1}{m+3}$ for $m\geq 3$. The theorem holds. Thus we suppose that $PV(B)\neq\emptyset$ in the following proof. In view of Lemma 4.3, it follows that there is a pendant vertex $y$ and an $m$-matching $M$ such that $y$ is not $M$-saturated. Let $xy\in E(B)$ and $d_{B}(x) = t$. Let $N_{B}(x)\cap PV(B) = \{y_{1}, y_{2}, \cdots, y_{r-1}, y_{r} = y\}$ and $N_{B}(x)\setminus PV(B) = \{u_{1}, u_{2}, \cdots, u_{t-r}\}$. Then $d_{B}(u_{i})\geq 2$ for each $i\in\{1, 2, \cdots, t-r\}$. Furthermore, since $B$ is a bicyclic graph and there exist at least $m-3$ $M$-saturated vertices in $V(B)\setminus\{x, y_{1}, y_{2}, \cdots, y_{r-1}, y_{r}, u_{1}, u_{2}, \cdots, u_{t-r}\}$, then $n = |V(B)|\geq t+1+m-3$, that is $t\leq n-m+2$. Let $B' = B-y$. Then $B'\in \boldsymbol{\mathscr{B}}_{n-1, m}$. We discuss in two cases.

Case 1. $r = 1$.

Now, $y = y_{1}$. By the induction hypothesis and Lemma 2.1, for $n > 2m$, it follows that

Case 2. $r\geq 2$.

Notice that there exist at least $r-1$ vertices which are not $M$-saturated, then $n-(r-1)\geq 2m$, that is $r\leq n-2m+1$. By the induction hypothesis and Lemmas 2.1, 2.4, it follows that

With the equalities hold only if $SDD(B') = g(n-1, m)$, $r = n-2m+1$, $t = n-m+2$ and $d_{U}(u_{j}) = 2$ for $j = 1, 2, \cdots, t-r$, which implies that $B'\cong \boldsymbol{B}^{*}_{n-1, m}$, and $B\cong \boldsymbol{B}^{*}_{n, m}$.

5.   Conclusions

Nowadays, finding bounds on any topological index with respect to different graph parameters is an important task. The research of mathematical properties on 20 discrete Adriatic indices selected as significant predictors of physical-chemical properties is one of open problems proposed by the International Academy of Mathematical Chemistry ^[4]. $SDD$ index is one of 20 discrete Adriatic indices. The mathematical properties of $SDD$ index deserve further study since it may be applied to detect the chemical compounds that may have desirable properties. $SDD$ index has been studied extensively since it was proved to be an applicable and viable molecular descriptor in 2018. Furthermore, unicyclic graphs and bicyclic graphs are two kinds of important graphs in mathematical chemistry. In this paper, by using the properties of $SDD$ index and exploring the structures of the unicyclic graphs and bicyclic graphs with given matching number, we present the maximum $SDD$ indices of unicyclic graphs and bicyclic graphs with given matching number, and identify the corresponding extremal graphs.

Acknowledgments

This work was supported by the Shanxi Province Science Foundation for Youths [grant number 201901D211227].

Conflict of interest

The authors declare no conflict of interest.