On the graph connectivity and the variable sum exdeg index

1.   Introduction

In this paper, we are concerned with undirected simple connected graphs only. Let $G = (V(G), E(G))$ denote a graph with vertex set $V(G)$ and edge set $E(G)$. The degree of a vertex $u\in V(G)$ is denoted by $d_{G}(u)$.

Topological indices are numbers reflecting certain structural features of organic molecules that are obtained from the molecular graph, and they play an important role in chemistry, pharmacology, etc. (see ^[1,2,3]). The Randić index ^[4] (devised in 1975 for measuring the branching of molecules) and Zagreb indices ^[5] (appeared in 1972 within the study of total $\pi$-electron energy on molecular structure) are among the most studied topological indices. The variable sum exdeg index (denoted by $SEI_{a}$) was introduced by Vukičević ^[6] in 2011 and is defined as:

where $a\neq 1$ is an arbitrary positive real number. This graph invariant is very well correlated with octanol-water partition coefficient of octane isomers ^[6], and was be used to analyze the octane isomers given by the International Academy of Mathematical Chemistry (IAMC) ^[7,8,9]. Yarahmadi and Ashrafi ^[10] presented a polynomial form of this descriptors with some applications in nanoscience. Applying the majorization technique, Ghalavand and Ashrafi ^[11] obtained the maximum and minimum values of variable sum exdeg index of trees, unicyclic, bicyclic and tricyclic graphs for $a > 1$. Recent results can be found in ^{[12,13,14,15]}.

Denote by $G-uv$ and $G+uv$ the graph that obtained from $G$ by deleting the edge $uv\in E(G)$ and the graph that obtained from $G$ by adding an edge $uv \notin E(G)$ ($u, v\in V(G)$), respectively. For $E'\subset E(G)$, let $G-E'$ be the subetaaph of $G$ obtained by deleting the edges of $E'$. Let $W\subset V(G)$, we use $G-W$ to denote the subetaaph of $G$ obtained by deleting the vertices of $W$ and the edges incident with them. A cut edge of a graph is an edge whose deletion breaks the graph into two components. A cut vertex in a connected graph is a vertex whose deletion increases the number of components of the graph. A block of a graph is a maximum connected subetaaph without cut vertices. We also call a block an endblock of a graph if it has at most one cut vertex in the graph as a whole. The vertex connectivity (respectively, edge connectivity) of a graph is the minimum number of vertices (respectively, minimum number of edges) whose deletion yields the resulting graph disconnected or a singleton. A clique of a graph $G$ is a subset $S$ of $V$ such that any two vertices in $G[S]$ (the subetaaph of $G$ induced by $S$) are adjacent. As usual, we use $P_{n}$, $S_{n}$, $C_{n}$ and $K_{n}$ to denote the $n$-vertex path, the $n$-vertex star, the $n$-vertex cycle and the $n$-vertex complete graph, respectively.

Let $P_{r} = x_{0}x_{1}\cdots x_{r}$ ($r\geq 1$) be a path of graph $G$ with $d_{G}(x_{1}) = \cdots = d_{G}(x_{r-1}) = 2$ (unless $r = 1$). If $d_{G}(x_{0}), d_{G}(x_{r})\geq 3$, then $P_{r}$ is called an internal path of $G$; if $d_{G}(x_{0})\geq 3, d_{G}(x_{r}) = 1$, then $P_{r}$ is called a pendant path of $G$. The vertex-disjoint union of the graphs $G_{1}$ and $G_{2}$ is denoted by $G_{1}\cup G_{2}$. Let $G_{1}\vee G_{2}$ be the graph obtained from $G_{1}\cup G_{2}$ by adding all possible edges from vertices of $G_{1}$ to vertices of $G_{2}$. The cyclomatic number of a connected graph $G$ is defined as $\gamma (G) = |E(G)|-|V(G)|+1$. A $k$ cyclic graph is a graph whose cyclomatic number is $k$. For $\gamma (G) = 0$, $G$ is a tree.

Let $K_{n}^{k}$ (as shown in Figure 1) be the graph obtained by identifying one vertex of $K_{n-k}$ with the central vertex of star $S_{k+1}$ and $C_{n}^{k}$ (as shown in Figure 1) be the graph obtained by attaching a pendant path $P_{k+1}$ to one vertex of $C_{n-k}$. Obviously, the graph $K_{n}^{k}$ and $C_{n}^{k}$ are two special graphs of order $n$ with $k$ cut edges.

The graph $G_{n, k}^{1}$ of order $n$ with $k$ cut vertices (as shown in Figure 2) is obtained from $K_{n-k}$ by attaching at most one pendant edge to each vertex of $K_{n-k}$, where $0 < k\leq \frac{n}{2}$.

The graph $G_{n, k}^{2}$ of order $n$ with $k$ cut vertices (as shown in Figure 2) is obtained from $K_{n-k}$ by attaching exactly one pendant path (with length equal or greater than one) to each vertex of $K_{n-k}$, where $\frac{n}{2} < k\leq n-3$, $l_{1}+l_{2}+\cdots+l_{m} = n-k$ and $l_{1}+2l_{2}+\cdots+ml_{m} = k$ ($l_{t}$ is the number of path with length $t$, $t = 1, 2, \cdots, m$). We can see ^[16] for other notations.

2.   Preliminaries

Lemma 2.1. ^[7] Let $f_{a}(x) = xa^{x}$, where $x\geq 1, a > 1$. Then

$(i) \; f_{a}(x)$ is an increasing function for each $a > 1$;

$(ii) \; f_{a}''(x) > 0$ and $f_{a}(x)$ is a convex function for each $a > 1$.

By Lemma 2.1 and the definition of variable sum exdeg index, the following Lemma 2.2 is obvious.

Lemma 2.2. Let $G = (V, E)$ be a simple connected graph. Then

$(i)$ If $e = uv\notin E(G), \ u, v\in V(G)$, $SEI_{a}(G) < SEI_{a}(G+e)$ for $a > 1$;

$(ii)$ If $e\in E(G)$, $SEI_{a}(G) > SEI_{a}(G-e)$ for $a > 1$.

Lemma 2.3. Let

where $x, y\geq 2$ and $a > 1$. Then $f(x, y) > 0$.

Proof. If $y\geq 2$ is fixed, by Lemma 2.1, we have

So $f(x, y)$ is strictly monotone increasing in $x$. By symmetry, if $x\geq 2$ is fixed, then $f(x, y)$ is strictly monotone increasing in $y$. Thus, by Jensen inequality for the function $xa^{x}$, which is strictly convex for $a > 1$, we have $f(x, y)\geq f(2, 2) = 3a^{3}+a-2\cdot 2a^{2} > 0$.

Lemma 2.4. Let

where $x\geq 2$, $r\geq 1$ and $a > 1$. Then $g(x)$ is strictly monotone increasing in $x$.

Proof. Note that for $a > 1$,

So $g(x)$ is strictly monotone increasing in $x$.

Lemma 2.5. Let

where $x\geq 2$, $y\geq 3$ and $a > 1$. Then $g(x, y)\geq 0$.

Proof. Since for $a > 1$,

So $g(x, y)$ is strictly monotone increasing in $x$. Thus, $g(x, y)\geq g(2, y) = 0$.

Lemma 2.6. Let

where $x, y\geq 3$ and $a > 1$. Then $h(x, y) > 0$.

Proof. Note that

So $h(x, y)$ is strictly monotone increasing in $x$. Thus, $h(x, y)\geq h(3, y) = ya^{y}-2a^{2}+(y-2)[ya^{y}-(y-1)a^{y-1}] > 0$.

Lemma 2.7. Let

where $x, y\geq 3$ and $a > 1$. Then $l(x, y) > 0$.

Proof. It can be seen that

So $l(x, y)$ is strictly monotone increasing in $x$. Thus, $l(x, y)\geq l(3, y) = (y-2)[ya^{y}-(y-1)a^{y-1}]+(y+1)a^{y+1}-3a^{3} > 0$.

3.   Variable sum exdeg indices of graphs with given number of cut edges for $a > 1$

We use $\textbf{G}_{E}(n, k)$ to denote the set of graphs on $n$ vertices with $k$ cut edges. If $k = n-1$, $\textbf{G}_{E}(n, n-1)$ is a tree and trees with extremal variable sum exdeg index had been obtained in ^[7] and ^[11]. For a connected graph on $n$ vertices having the cyclomatic number at least one, the number of its cut edges is at most $n-3$. Therefore, in this section, we always assume that $G$ has $k$ cut edges with $1 \leq k \leq n -3$.

3.1.   The largest variable sum exdeg index of a graph with given number of cut edges for $a > 1$

First, we provide some graph transformations on graphs with given number of cut edges which will increase the variable sum exdeg index for $a > 1$.

Transformation $A_{1}$: Suppose $G_{1}$ is a graph with $n_{1}\geq 3$ vertices and $G_{2}$ is a graph with $n_{2} \geq 2$ vertices, where $G_{1}$ is 2-edge connected. Let $G$ be a graph obtained from $G_{1}$ and $G_{2}$ by adding an edge between a vertex $x$ of $G_{1}$ and a vertex $y$ of $G_{2}$, as shown in Figure 3. Then $xy$ be a non-pendant cut edge of $G$. Let $G'$ be the graph obtained by identifying $x$ of $G_{1}$ to $y$ of $G_{2}$ and adding a pendant edge to $x(y)$, as shown in Figure 3.

Lemma 3.1. Let $G$ and $G'$ be graphs in Figure 3. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. Let $d_{G}(x) = r$ and $d_{G}(y) = s$. By the definition of variable sum exdeg index and Lemma 2.3, we have

The proof is completed.

Remark 3.2. For any $G\in {\textbf{G}}_{E}(n, k)$, if necessary, by repeating the graph transformation $A_{1}$, any cut edge (non-pendant cut edge) of $G$ can changed into pendant edge. That is, if necessary, by a series of transformation $A_{1}$, we can change $G$ to $G^{*}$ (as shown in Figure 4), where $S_{i}\ (1 \leq i \leq r)$ are 2-edge-connected graphs.

Transformation $A_{2}$: Let $G$ be a graph as shown in Figure 5, $x, y\in V(G_{1})$, $x_{1}, x_{2}, \cdots, x_{r}$ are pendant vertices adjacent to $x$, and $y_{1}, y_{2}, \cdots, y_{s}$ are pendant vertices adjacent to $y$, where $d_{G}(y)\leq d_{G}(x)$. Let $G' = G-\{yy_{1}, yy_{2}, \cdots, yy_{s}\}+\{xy_{1}, xy_{2}, \cdots, xy_{s}\}$, as shown in Figure 5.

Lemma 3.3. Let $G$ and $G'$ be graphs in Figure 5. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. In view of the definition of variable sum exdeg index and Lagrange mean value theorem, for $a > 1$, we have

where $d_{G}(x) < \xi < d_{G}(x)+s$, $d_{G}(y)-s < \eta < d_{G}(y)$.

Since $d_{G}(y)\leq d_{G}(x)$, by Lemma 2.1, then $SEI_{a}(G')-SEI_{a}(G) > 0$, i.e., $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Remark 3.4. For any $G \in {\textbf{G}}_{E}(n, k)$, if necessary, by repeating graph transformation $A_{1}$ and $A_{2}$, all the pendant edges are attached to the same vertex. That is, if necessary, by a series of transformation $A_{1}$ and $A_{2}$, we can change $G$ to $H_{1}$ or $H_{2}$ (as shown in Figure 6), where $S_{i}\ (1 \leq i \leq r)$ are 2-edge-connected graphs.

By Lemmas 3.1, 3.3 and Remarks 3.2, 3.4, we have the following Lemma 3.5.

Lemma 3.5. Let $G\in {\textbf{G}}_{E}(n, k)$. Then $SEI_{a}(G)\leq SEI_{a}(H_{i}) \; (i = 1$ or $2)$ for $a > 1$, where $H_{1}$ or $H_{2}$ is a graph as shown in Figure 6, $S_{i} \; (1\leq i \leq r)$ are 2-edge-connected graphs.

Denoted $K_{n_{i}} \; (1\leq i \leq r)$ to be a clique which is obtained by adding edges in $S_{i} \; (1\leq i \leq r)$ and changing $S_{i}$ into complete sub-graphs, where $S_{i} \; (1\leq i \leq r)$ in $H_{1}$ or $H_{2}$ are 2-edge-connected graphs.

Lemma 3.6. Suppose $H_{1}'$ or $H_{2}'$ is a graph as shown in Figure 7, where $K_{n_{i}} \; (1\leq i \leq r)$ is a clique as above. Then $SEI_{a}(H_{i}')\geq SEI_{a}(H_{i}) \; (i = 1$ or $2)$ for $a > 1$.

Proof. By Lemma 2.2, the result holds obviously.

Theorem 3.7. Let $G\in {\textbf{G}}_{E}(n, k)$, where $1\leq k\leq n-3$. Then

for $a > 1$, with equality holding if and only if $G\cong K_{n}^{k}$.

Proof. Choose $G\in \textbf{G}_{E}(n, k)$ such that $G$ has the maximum variable sum exdeg index for $a > 1$. By Lemma 3.5 and 3.6, we have $SEI_{a}(G)\leq SEI_{a}(H_{1}')$ or $SEI_{a}(G)\leq SEI_{a}(H_{2}')$ for $a > 1$.

Next, we prove that $r = 1$. By contradiction, assume that $r\geq 2$. Without loss of generality, suppose that there exists an edge $e = uv \notin E(G)$, $u\in V(K_{n_{i}})$, $v\in V(K_{n_{j}})$, $1\leq i, j\leq r$, $i\neq j$, and $u, v$ is not the common vertex of $K_{n_{i}}$ and $K_{n_{j}}$. By Lemma 2.2, we have $SEI_{a}(G+e) > SEI_{a}(G)$ for $a > 1$, a contradiction to the choice of $G$. So $r = 1$, i.e., $G\cong K_{n}^{k}$.

3.2.   The smallest variable sum exdeg index of a graph with given number of cut edges for $a > 1$

First, we provide some transformations on graphs with cut edges which will decrease the variable sum exdeg index for $a > 1$.

Transformation $A_{3}$: Let $C_{p} = u_{0}u_{1}u_{2}\cdots u_{p-1}$ and $C_{q} = v_{0}v_{1}v_{2}\cdots v_{q-1}$ be two cycles in $G$ (as shown in Figure 8) such that $C_{p}$ connects $C_{q}$ by a path $P_{l}$ (with $l\geq 2$ vertices) whose end vertices are $u_{0}, \ v_{1}$, and the vertex, say $u_{t}$ (resp. $v_{s}$), on the cycle $C_{p}$ (resp. $C_{q}$) in $G$ either is of degree 2 or has subetaaph $G_{t}$ (resp. $H_{s})$ attached, $0\leq t\leq p-1$, $0\leq s\leq q-1$. $G' = G-\{u_{0}u_{1}, v_{1}v_{0}, v_{1}v_{2}\}+\{u_{0}v_{2}, u_{1}v_{0}\}$, as shown in Figure 8.

Lemma 3.8. Let $G$ and $G'$ be graphs in Figure 8. Then $SEI_{a}(G) > SEI_{a}(G')$ for $a > 1$.

Proof. It is easy to see that $d_{G'}(u_{0}) = d_{G}(u_{0})$, $d_{G'}(u_{1}) = d_{G}(u_{1})$, $d_{G'}(v_{0}) = d_{G}(v_{0})$, $d_{G'}(v_{2}) = d_{G}(v_{2})$, $d_{G'}(v_{1}) = d_{G}(v_{1})-2$, and $d_{G'}(w) = d_{G}(w)$ for $w\in V(G)\backslash \{u_{0}, u_{1}, v_{0}, v_{1}, v_{2}\}$. Thus, for $a > 1$,

The proof is completed.

Transformation $A_{4}$: Let $G$ be a graph as shown in Figure 9, where $G_{1}\ncong K_{1}$ and $y\in V(G_{1})$. That is, we use $G$ to denote the graph obtained from $G_{1}$ by identifying $y$ with the vertex $x_{r}$ of a path $x_{1}x_{2}\cdots x_{r-1}x_{r}\cdots x_{n}$, $1 < r < n$. Let $G' = G-x_{r-1}x_{r}+x_{n}x_{r-1}$, as shown in Figure 9.

Lemma 3.9. Let $G$ and $G'$ be graphs in Figure 9. Then $SEI_{a}(G) > SEI_{a}(G')$ for $a > 1$.

Proof. By Lemma 2.1 and the definition of variable sum exdeg index, we have

where $d_{G_{1}}(y)+1 < \xi < d_{G_{1}}(y)+2$, $1 < \eta < 2$.

Remark 3.10. By repeating Transformation $A_{5}$, any tree $T$ attached to a graph $G$ can be changed into a path as showed in Figure 10.

Transformation $A_{5}$: Let $G$ be a graph as shown in Figure 11, where $x, y\in V(G_{1})$ and $d_{G_{1}}(x), d_{G_{1}}(y)\geq 2$. That is, we use $G$ to denote the graph obtained from identifying $x$ with the vertex $x_{0}$ of a path $x_{0}x_{1}\cdots x_{r}$ and identifying $y$ with the vertex $y_{0}$ of a path $y_{0}y_{1}\cdots y_{s}$, where $r, s\geq 1$. $G^{'} = G-xx_{1}+y_{s}x_{1}$, as shown in Figure 11.

Lemma 3.11. Let $G$ and $G'$ be graphs in Figure 11. Then $SEI_{a}(G) > SEI_{a}(G')$ for $a > 1$.

Proof. The proof is similar to Lemma 3.9, omitted.

Theorem 3.12. Let $G\in {\textbf{G}}_{E}(n, k)$, where $1\leq k\leq n-3$. Then

for $a > 1$, with equality holding if and only if $G\cong C_{n}^{k}$.

Proof. Choose connected graph $G\in \textbf{G}_{E}(n, k)$ such that it has the smallest variable sum exdeg index for $a > 1$. Let $E' = \{e_{1}, e_{2}, \cdots, e_{k}\}$ be the set of the cut edges of $G\in \textbf{G}_{E}(n, k)$. By Lemma 2.2, it can be seen that each component of $G-E'$ is either a cycle or an isolated vertex.

Next, we prove that $G$ contains exactly one cycle of length $n-k$. By contradiction, assume that $G$ contains at least two cycles. Then by Lemma 3.8, we can obtain a graph $G'\in \textbf{G}_{E}(n, k)$ such that $SEI_{a}(G') < SEI_{a}(G)$ for $a > 1$, a contradiction to the choice of $G$. Furthermore, $G$ has $k$ cut edges, so the length of the cycle contained in $G$ is of $n-k$. By Lemmas 3.9, 3.11 and Remark 3.10, we have $G\cong C_{n}^{k}$.

4.   Variable sum exdeg indices of graphs with given number of cut vertices for $a > 1$

Let $\textbf{G}_{V}(n, k)$ be the set of graphs on $n$ vertices with $k$ cut vertices. If $k = n-2$, then the only graph in $\textbf{G}_{V}(n, n-2)$ is the path. Therefore, in this section, we always assume that $G$ has $k$ cut vertices with $1 \leq k \leq n -3$.

Transformation $B_{1}$: Let $G$ be a graph as shown in Figure 12, $K_{p}$ and $K_{q}$ be two cliques of $G$, where $p\geq 2$, $q \geq 3$ and $K_{q}$ is an endblock. $V(K_{p})$ and $V(K_{q})$ have one cut vertex, say $u$, in common. $V(K_{p}) = \{u_{1}, u_{2}, \cdots, u_{p-1}, u\}$, $V(K_{q}) = \{v_{1}, v_{2}, \cdots, v_{q-1}, u\}$. $G_{i} \; (1\leq i\leq p-1)$ is the subetaaph attached to $u_{i} \; (1\leq i\leq p-1)$. Let $G' = G-\{uu_{1}, uu_{2}, \cdots, uu_{p-1}, uv_{2}, uv_{3}, \cdots, uv_{q-1}\}+\{u_{1}v_{1}, u_{1}v_{2}, \cdots, u_{1}v_{q-1}\}+\cdots+\{u_{p-1}v_{1}, u_{p-1}v_{2}, \cdots, u_{p-1}v_{q-1}\}$, as shown in Figure 12.

Lemma 4.1. Let $G$ and $G'$ be graphs in Figure 12. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. Note that $d_{G}(u) = p+q-2$, $d_{G'}(u) = 1$, $d_{G}(v_{1}) = q-1$, $d_{G'}(v_{1}) = p+q-2$, $d_{G'}(u_{i}) = d_{G}(u_{i})+q-2$ ($i = 1, 2, \cdots, p-1$), $d_{G'}(v_{j}) = p+q-3$ ($j = 2, 3, \cdots, q-1$), and the degrees of other vertices in $G_{i} \; (1\leq i\leq p-1)$ are unchanged. By the definition of variable sum exdeg index and Lemma 2.4, 2.5, for $a > 1$, we have

This completes the proof.

Transformation $B_{2}$: Let $G$ be a graph as shown in Figure 13, $K_{p}$ be a clique of $G$, where $p\geq 3$. $V(K_{p}) = \{u_{0}, u_{1}, \cdots, u_{p-1}\}$. $P = u_{1}w_{1}\cdots w_{t}\ (t\geq 2)$ is a path attached to $u_{1}$. $N_{G}(u_{0}) = \{u_{1}, u_{2}, \cdots, u_{p-1}\}$, $N_{G}(u_{1}) = \{u_{0}, u_{2}, \cdots, u_{p-1}, w_{1}\}$. $G_{i} \; (2\leq i\leq p-1)$ is the subetaaph attached to $u_{i} \; (2\leq i\leq p-1)$. Let $G' = G-w_{t-1}w_{t}+u_{0}w_{t}$, as shown in Figure 13.

Lemma 4.2. Let $G$ and $G'$ be graphs in Figure 13. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. By the definition of variable sum exdeg index and Lemma 2.4, for $a > 1$, we have

The proof is completed.

Transformation $B_{3}$: Let $G$ be a graph as shown in Figure 14, $K_{p}$ and $K_{q}$ be two cliques of $G$, where $p, q\geq 3$. $V(K_{p})$ and $V(K_{q})$ have one cut vertex, say $u$, in common. $V(K_{p}) = \{u_{1}, u_{2}, \cdots, u_{p-1}, u\}$, $V(K_{q}) = \{v_{1}, v_{2}, \cdots, v_{q-1}, u\}$. $P = v_{1}w_{1}\cdots w_{t}\ (t\geq 1)$ is a path attached to $v_{1}$ and $N_{G}(v_{1}) = \{u, v_{2}, \cdots, v_{q-1}, w_{1}\}$. $G_{i} \; (1\leq i\leq p-1)$ is the subetaaph attached to $u_{i} \; (1\leq i\leq p-1)$ and $H_{j} \; (2\leq j\leq q-1)$ is the subetaaph attached to $v_{j} \; (2\leq j\leq q-1)$. Let $G' = G-\{uu_{1}, uu_{2}, \cdots, uu_{p-1}, uv_{1}, uv_{2}, \cdots, uv_{q-1}\}+\{w_{t}u\}+\{u_{1}v_{1}, u_{1}v_{2}, \cdots, u_{1}v_{q-1}\}+ \cdots+\{u_{p-1}v_{1}, u_{p-1}v_{2}, \cdots, u_{p-1}v_{q-1}\}$, as shown in Figure 14.

Lemma 4.3. Let $G$ and $G'$ be graphs in Figure 14. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. It can be seen that $d_{G}(u) = p+q-2$, $d_{G'}(u) = 1$, $d_{G}(w_{t}) = 1$, $d_{G'}(w_{t}) = 2$, $d_{G}(v_{1}) = q$, $d_{G'}(v_{1}) = p+q-2$, $d_{G'}(u_{i}) = d_{G}(u_{i})+q-2$ ($i = 1, 2, \cdots, p-1$), $d_{G'}(v_{j}) = d_{G}(v_{j})+p-2$ ($j = 2, \cdots, q-1$), and the degrees of other vertices are unchanged. By the definition of variable sum exdeg index and Lemma 2.4, 2.6, for $a > 1$, we have

The proof is completed.

Transformation $B_{4}$: Let $G$ be a graph as shown in Figure 15, $K_{p}$ and $K_{q}$ be two cliques of $G$, where $p, q\geq 3$. $K_{p}$ connects $K_{q}$ by an internal path $P = u\cdots u'$ of length $s\geq 1$. $V(K_{p}) = \{u_{1}, u_{2}, \cdots, u_{p-1}, u\}$, $V(K_{q}) = \{v_{1}, v_{2}, \cdots, v_{q-1}, u'\}$. $P_{t+1} = v_{1}w_{1}\cdots w_{t}\ (t\geq 1)$ is a path attached to $v_{1}$ and $N_{G}(v_{1}) = \{u', v_{2}, \cdots, v_{q-1}, w_{1}\}$. $G_{i} \; (1\leq i\leq p-1)$ is the subetaaph attached to $u_{i} \; (1\leq i\leq p-1)$ and $H_{j} \; (2\leq j\leq q-1)$ is the subetaaph attached to $v_{j} \; (2\leq j\leq q-1)$. Let $G' = G-\{uu_{1}, uu_{2}, \cdots, uu_{p-1}, u'v_{1}, u'v_{2}, \cdots, u'v_{q-1}\}+\{w_{t}u\}+\{u_{1}v_{1}, u_{1}v_{2}, \cdots, u_{1}v_{q-1}\}+\cdots+\{u_{p-1}v_{1}, u_{p-1}v_{2}, \cdots, u_{p-1}v_{q-1}\}$, as shown in Figure 15.

Lemma 4.4. Let $G$ and $G'$ be graphs in Figure 15. Then $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Proof. We notice that $d_{G}(u) = p$, $d_{G'}(u) = 2$, $d_{G}(u') = q$, $d_{G'}(u') = 1$, $d_{G}(w_{t}) = 1$, $d_{G'}(w_{t}) = 2$, $d_{G}(v_{1}) = q$, $d_{G'}(v_{1}) = p+q-2$, $d_{G'}(u_{i}) = d_{G}(u_{i})+q-2$ ($i = 1, 2, \cdots, p-1$), $d_{G'}(v_{j}) = d_{G}(v_{j})+p-2$ ($j = 2, \cdots, q-1$), and the degrees of other vertices are unchanged. By the definition of variable sum exdeg index and Lemma 2.4, 2.7, for $a > 1$, we have

This finishes the proof.

Lemma 4.5. Choose $G\in {\textbf{G}}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. Then each cut vertex of $G$ connects exactly two blocks and each of the blocks contained in $G$ is a clique.

Proof. We shall prove by contradiction. Let $u$ be a cut vertex in $G$. Assume that $u$ connects at least three connected components, say $G_{1}, G_{2}, \cdots, G_{r} \; (r\geq 3)$, of $G$. Let $G' = G+xy$, where $x\in V(G_{2})\backslash \{u\}$ and $y\in V(G_{3})\backslash \{u\}$. Clearly, $G'\in\textbf{G}_{V}(n, k)$ and by Lemma 2.2, we have $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$, a contradiction. Thus, we get that each cut vertex connects exactly two blocks. Moreover, by Lemma 2.2, we can conclude that each block is a clique.

In order to determine the maximum variable sum exdeg index of $\textbf{G}_{V}(n, k)$, we choose connected graph $G\in \textbf{G}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. By Lemma 4.5, each cut vertex of $G$ connects exactly two cliques. We define two cliques $K_{p}$, $K_{q}$ ($p, q\geq 3$) of $G$ are adjacent, if $K_{p}$ connects $K_{q}$ by a path $P$ such that $P$ does not intersect some other clique with at least 3 vertices. By Lemma 4.5, the following Lemma 4.6 is obtained.

Lemma 4.6. Choose $G\in {\textbf{G}}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. If two cliques $K_{p}$, $K_{q}$ with $p, q\geq 3$ in $G$ are adjacent, then the path connecting $K_{p}$ and $K_{q}$ is either of length 0 or an internal path.

Lemma 4.7. Choose $G\in {\textbf{G}}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. If $K_{q}$ is an endblock of $G$, then $q = 2$.

Proof. We prove this lemma by contradiction. Suppose that $q\geq 3$, let $K_{p} \; (p\geq 2)$ be a clique such that $V(K_{p})$, $V(K_{q})$ have one cut vertex, say $u$, in common. By Lemma 4.5, $u$ is not a cut vertex of some other clique. From Lemma 4.1, $G$ can be changed to $G'$ by transformation $B_{1}$ with a larger variable sum exdeg index for $a > 1$, which contradicts the choice of $G$. Hence, $q = 2$.

Choose $G\in \textbf{G}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. By Lemma 4.5, we assume that $K_{n_{1}}, K_{n_{2}}, \cdots, K_{n_{r}}$ are all cliques of $G$.

Lemma 4.8. Choose $G\in {\textbf{G}}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. Let $K_{n_{1}}, K_{n_{2}}, \cdots, K_{n_{r}}$ are all of the cliques contained in $G$. Then there is only one clique $K_{n_{i}}$ with $n_{i}\geq 3$.

Proof. To the contrary, suppose that there are two cliques $K_{p}$, $K_{q} \; (p\neq q$ and $p, q\in \{n_{1}, n_{2}, \cdots, \; n_{r}\})$ such that $K_{p}$ is adjacent to $K_{q}$, where $p, q \geq 3$. By Lemma 4.7, it can be seen that $K_{p}$ and $K_{q}$ are not endblocks. Furthermore, by Lemma 4.5, we can choose two such blocks such that at least one of them have a pendant path attached to one of its vertices. Without loss of generality, we assume that $K_{q}$ is one of such cliques and $v_{1}$ is attached by one pendant path, say $P_{t+1} = v_{1}w_{1} \cdots w_{t} \; (t\geq 1)$. By Lemma 4.6, we can see that $K_{p}$ and $K_{q}$ have exactly one cut vertex in common or $K_{p}$ connects $K_{q}$ by an internal path $P$ of length $s\geq 1$. Next, We discuss in two cases.

Case 1. $K_{p}$ and $K_{q}$ have exactly one cut vertex, say $u$, in common.

By Lemma 4.3, $G$ can be changed to $G'$ by transformation $B_{3}$ with a larger variable sum exdeg index for $a > 1$, which is a contradiction to the choice of $G$.

Case 2. The internal path $P = u\cdots u'$ is of length $s\geq 1$.

By Lemma 4.4, $G$ can be changed to $G'$ by transformation $B_{4}$ with a larger variable sum exdeg index for $a > 1$, which contradicts the assumption of $G$.

The proof is completed.

Lemma 4.9. Choose $G\in {\textbf{G}}_{V}(n, k)$ such that $SEI_{a}(G)$ is as large as possible for $a > 1$. Let $K_{p}$ be the only clique with $p\geq 3$. Then $p = n-k$.

Proof. In view of Lemma 4.5 and 4.8, it can be concluded that in $G$, there are $k+1$ cliques and $k$ of them are isomorphic to $K_{2}$. Since $G$ has $k$ cut vertices, and each cut vertex belongs to two cliques, then $2k+p-k = n$. Thus, $p = n-k$.

Denote $\mathcal{\textbf{G}}_{n, k} = \{G | G\in \textbf{G}_{V}(n, k)$ is obtained by attaching at most one pendant path to each vertex of $K_{n-k}\}$. Then it is not difficult to see that $\{G_{n, k}^{1}, G_{n, k}^{2}\}\subset \mathcal{\textbf{G}}_{n, k}$.

Lemma 4.10. Let $H\in {\textbf{G}}_{n, k}$. Then for $a > 1$, the maximum value of $SEI_{a}(H)$ is obtained at the graph in $G_{n, k}^{1}$ or $G_{n, k}^{2}$.

Proof. Choose $H\in \mathcal{\textbf{G}}_{n, k}$ such that $SEI_{a}(H)$ is as large as possible for $a > 1$. If $H\cong G_{n, k}^{1}$ or $G_{n, k}^{2}$, the lemma holds. Otherwise, $H\in \mathcal{\textbf{G}}_{n, k}\backslash \{G_{n, k}^{1}, G_{n, k}^{2}\}$. Let $P$, which is attached to $u_{0}$, be the shortest path of all the pendant paths in $H$ and $P'$, which is attached to $u_{1}$, be the longest one in $H$. Since $H\notin \{G_{n, k}^{1}, G_{n, k}^{2}\}$, then we have $|E(P)| = 0$ ($H$ has no pendant path attached to $u_{0}$) and $|E(P')|\geq 2$. By Lemma 4.2, $H$ can be changed to $H'$ by transformation $B_{2}$ with a larger variable sum exdeg index for $a > 1$, which contradicts the assumption of $H$.

Theorem 4.11. Let $G\in {\textbf{G}}_{V}(n, k)$, where $1\leq k\leq n-3$. Then

$(i)$ if $1\leq k\leq \frac{n}{2}$, $SEI_{a}(G)\leq (n-2k)(n-k-1)a^{n-k-1}+k(n-k)a^{n-k}+ka$ for $a > 1$, with equality holding if and only if $G\cong G_{n, k}^{1}$;

$(ii)$ if $\frac{n}{2} < k\leq n-3$, $SEI_{a}(G)\leq (n-k)^{2}(n-k-1)a^{n-k-1}+2(2k-n)a^{2}+a(n-k)$ for $a > 1$, with equality holding if and only if $G\cong G_{n, k}^{2}$.

Proof. By Lemma 4.8 and 4.9, we have $G\in \mathcal{\textbf{G}}_{n, k}$. By Lemma 4.10, for $a > 1$, we have $SEI_{a}(G)\leq SEI_{a}(G_{n, k}^{1})$ when $1\leq k\leq \frac{n}{2}$ and $SEI_{a}(G)\leq SEI_{a}(G_{n, k}^{2})$ when $\frac{n}{2} < k\leq n-3$.

The proof is finished.

5.   Variable sum exdeg indices of graphs with given vertex connectivity or edge connectivity for $a > 1$

Lemma 5.1. Let $G$ be a graph of order $n$ with vertex connectivity $\kappa < n-1$. Then there exist positive integers $n_{1}$ and $n_{2}$ such that $n_{1}+n_{2} = n-\kappa$ and for $a > 1$,

Proof. Assume that $X$ is a vertex cut of $G$ with $\kappa$ vertices such that $G-X$ has $l$ components, say $G_{1}, G_{2}, \cdots, G_{l}$, where $l\geq 2$. Let $n_{1} = |V(G_{1})|$ and $n_{2} = |V(G_{2}\cup\cdots\cup G_{l})|$. Then $G$ is a spanning subetaaph of $K_{\kappa}\vee (K_{n_{1}}\cup K_{n_{2}})$. By Lemma 2.2, the lemma holds immediately.

Lemma 5.2. Let $G$ be a $n$-vertex graph with edge connectivity $\lambda < n-1$. Then there exist positive integers $n_{1}$ and $n_{2}$ such that $n_{1}+n_{2} = n-\kappa$, $\kappa\leq \lambda$ and for $a > 1$,

Proof. Let $\kappa$ be the vertex connectivity of $G$. Then $\kappa\leq \lambda < n-1$. From Lemma 5.1, the conclusion holds clearly.

Lemma 5.3. Let $G = K_{s}\vee (K_{n_{1}}\cup K_{n_{2}})$ and $G' = K_{s}\vee (K_{n_{1}-1}\cup K_{n_{2}+1})$, where $2\leq n_{1}\leq n_{2}$, $n_{1}+n_{2} = n-s$. Then for $a > 1$,

Proof. In view of the definition of variable sum exdeg index, for $a > 1$, we have

where $n_{2}+s-1 < \xi < n_{2}+s$, $n_{1}+s-2 < \eta < n_{1}+s-1$. By Lemma 2.1, we have $SEI_{a}(G')-SEI_{a}(G) > 0$ for $a > 1$, i.e., $SEI_{a}(G') > SEI_{a}(G)$ for $a > 1$.

Theorem 5.4. Let $G$ be a graph of order $n$ with vertex connectivity $\kappa \; (\kappa < n-1)$. Then

for $a > 1$, with equality if and only if $G\cong K_{\kappa}\vee (K_{1}\cup K_{n-\kappa-1})$.

Proof. Choose $G$ such that $G$ has the maximum variable sum exdeg index (for $a > 1$) among all graphs of order $n$ with vertex connectivity $\kappa$. By Lemma 2.2 and 5.1, there exist positive integers $n_{1}$ and $n_{2}$ such that $n_{1}+n_{2} = n-\kappa$ and $G\cong K_{\kappa}\vee (K_{n_{1}}\cup K_{n_{2}})$. Moreover, by Lemma 5.3, $G\cong K_{\kappa}\vee (K_{1}\cup K_{n-\kappa-1})$.

Theorem 5.5. Let $G$ be a $n$-vertex graph with edge connectivity $\lambda \; (\lambda < n-1)$. Then

for $a > 1$, with equality if and only if $G\cong K_{\lambda}\vee (K_{1}\cup K_{n-\lambda-1})$.

Proof. Choose $G$ such that $G$ has the maximum variable sum exdeg index (for $a > 1$) among all $n$-vertex graphs with edge connectivity $\lambda$. By Lemma 2.1 and 5.2, there exist positive integers $\kappa\leq \lambda$ such that $n_{1}+n_{2} = n-\kappa$ and $G\cong K_{\kappa}\vee (K_{n_{1}}\cup K_{n_{2}})$. By Lemma 5.3, we have $G\cong K_{\kappa}\vee (K_{1}\cup K_{n-\kappa-1})$. Furthermore, $K_{\kappa}\vee (K_{1}\cup K_{n-\kappa-1})$ is a spanning subetaaph of $K_{\lambda}\vee (K_{1}\cup K_{n-\lambda-1})$ for $\kappa\leq \lambda$, by Lemma 2.2, the result holds obviously.

6.   Conclusions

In ^[7], Vukičević think that mathematical properties of the variable sum exdeg index deserves further study since it can be used for the detection of chemical compounds that may have desirable properties. Inspired by ^{[17,18,19,20,21,22,23,24]}, we continue to study the mathematical properties of the variable sum exdeg index and the connectivity of a graph. In this work, we present the extremal value of the variable sum exdeg indices (for $a > 1$) in terms of the number of cut edges, or the number of cut vertices, or the vertex connectivity, or the edge connectivity of a graph. Furthermore, the corresponding extremal graphs are characterized.

Acknowledgments

The authors would like to thank the referees for their careful reading and helpful suggestions. 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.