#  The $Q$-index and connectivity of graphs††thanks:  This work is supported
by the National Natural Science Foundation of China (Nos. 11971311, 12026230);
L. Feng and W. Liu were supported by NSFC (Nos. 11871479, 12071484), Hunan
Provincial Natural Science Foundation (2020JJ4675, 2018JJ2479). E-mail
addresses<EMAIL_ADDRESS>(P.-L. Zhang<EMAIL_ADDRESS>(L. Feng),
wjliu6210@126.com(W. Liu<EMAIL_ADDRESS>(†X.-D. Zhang, corresponding
author).

Peng-Li Zhanga, Lihua Fengb, Weijun Liub, Xiao-Dong Zhang${}^{a}\dagger$
a School of Mathematical Sciences, Shanghai Jiao Tong University,
800 Dongchuan Road, Shanghai, 200240, PR China
b School of Mathematics and Statistics, Central South University,
New Campus, Changsha, Hunan, 410083, PR China

###### Abstract

A connected graph $G$ is said to be $k$-connected if it has more than $k$
vertices and remains connected whenever fewer than $k$ vertices are deleted.
In this paper, for a connected graph $G$ with sufficiently large order, we
present a tight sufficient condition for $G$ with fixed minimum degree to be
$k$-connected based on the $Q$-index. Our result can be viewed as a spectral
counterpart of the corresponding Dirac type condition.

Key words: $Q$-index; Minimum degree; $k$-connected.

AMS subject classifications: 05C50; 05C40.

##  1 Introduction

All graphs considered in this paper are simple connected and undirected. The
notations we used are standard. Let $G$ be a simple connected graph with
vertex set $V(G)$ and edge set $E(G)$ such that $|V(G)|=n$ and $|E(G)|=m$. Let
$d(v)$ be the degree of a vertex $v$ in $G$, and the minimum degree be
$\delta(G)=\delta$. For two vertex-disjoint graphs $G$ and $H,$ we denote
$G\cup H$ the disjoint union of $G$ and $H,$ $G\vee H$ the join of $G$ and
$H,$ which is a graph obtained by adding all possible edges between $G$ and
$H.$ Throughout this paper, we use the symbol $i\sim j$ to denote the vertices
$i$ and $j$ are adjacent, and $i\nsim j$ otherwise.

A graph $G$ is said to be _$k$ -connected_ if it has more than $k$ vertices
and remains connected whenever fewer than $k$ vertices are deleted. In the
meantime, a vertex-cut $X$ of $G$ is a subset of $V(G)$ such that $G-X$ is
disconnected. The vertex connectivity $\kappa$ is the minimum vertex-cut $X.$
We say $G$ is $k$-connected when $\kappa\geq k,$ $\kappa=0$ if $G$ is either
trivial or disconnected. In other words, $G$ is $k$-connected if the minimum
vertex-cut $X$ satisfies $|X|\geq k.$

The _adjacency matrix_ of $G$ is $A(G)=(a_{ij})_{n\times n}$ with $a_{ij}=1$
if $i$ and $j$ are adjacent, and $a_{ij}=0$ otherwise. The largest eigenvalue
of $A(G)$, denoted by $\lambda(G)$, is called the spectral radius of $G$. The
_diagonal matrix_ of $G$ is $D(G)=(d_{ii})_{n\times n},$ whose diagonal
entries $d_{ii}$ satisfy $d_{ii}=d(i)$. The _signless Laplacian matrix_ $Q(G)$
of $G$ is defined as $D(G)+A(G).$ The largest eigenvalue of $Q(G)$, denoted by
$q(G)$, is called the $Q$-index (or the signless Laplacian spectral radius) of
$G$.

When one talks about spectral graph theory, perhaps one of the most well-known
problems is the Brualdi-Solheid problem [3]: Given a set ${\cal{G}}$ of
graphs, find a tight upper bound for the spectral radius in ${\cal{G}}$ and
characterize the extremal graphs. This problem is well studied in the
literature for various classes of graphs, such as graphs with given number of
cut vertices or cut edges [1, 21], graphs with given edge chromatic number
[6]. For the $Q$-index counterpart of the above problem, Zhang [31] gave the
$Q$-index of graphs with given degree sequence, Zhou [32] studied the
$Q$-index and Hamiltonicity. Also, from both theoretical and practical
viewpoint, the eigenvalues of graphs have been successfully used in many other
disciplines, one may refer to [15, 17, 18, 29, 30].

Analogous to the Brualdi–Solheid problem, the following problem was proposed
[25]: What is the maximum spectral radius of a graph $G$ on $n$ vertices
without a subgraph isomorphic to a given graph $F$? Regarding this problem,
Fiedler and Nikiforov [12] obtained tight sufficient conditions for graphs to
be hamiltonian or traceable. This motivates further study for such questions.
Later, Zhou [32] considered the $Q$-index version of the results in [12]. For
further reading in this topic, see [7, 8, 9, 19, 22, 23, 24, 27, 33, 34].

For the connectivity and eigenvalues of graphs, one must mention the classical
result from Fiedler [11] which states that the second smallest Laplacian
eigenvalue is at most the connectivity for any non-complete graph, which now
becomes one of the most attractive research areas. For adjacency eigenvalues,
extending the result in [4], Cioabǎ [5] obtained

###### Theorem 1.1

Let $d\geq k\geq 2$. If the second largest eigenvalue $\lambda_{2}$ of a
$d$-regular graph satisfies

$\lambda_{2}<d-\frac{(k-1)n}{(d+1)(n-d-1)},$

then the edge-connectivity of $G$ is at least $k$.

There are also several related results regarding the edge-connectivity and
eigenvalues of graphs, which can be found in [13, 20, 28].

One of the classical problems of graph theory is to obtain sufficient
conditions for a graph possessing certain properties. It is known that [2,
Page 4], if $G$ is a simple graph of order $n\geq k+1$, and if

$\delta\geq\frac{1}{2}(n+k-2),$

then $G$ is $k$-connected. In this paper, borrowing ideas from [19, 26], by
utilizing the $Q$-index, we will establish a new sufficient condition for
graphs with fixed minimum degree to be $k$-connected, for sufficiently large
order (and therefore for relatively small $\delta$). Such results may be of
independent interest. For any $k>1$ and $n>2k+1,$ let

${M}_{k}(n)=K_{k}\vee(K_{n-2k}\cup\overline{K_{k}}).$

For any $k\geq 1$ and $n\geq k+2,$ let

${L}_{k}(n)=K_{1}\vee(K_{n-k-1}\cup{K_{k}}).$

In light of the result of Li and Ning [16], Nikiforov [26] proved the
following theorem.

###### Theorem 1.2

Let $k>1,$ $n\geq k^{3}+k+4,$ and let $G$ be a graph of order $n$ with minimum
degree $\delta(G)\geq k$. If

$\lambda(G)\geq n-k-1,$

then $G$ has a Hamiltonian cycle unless $G={M}_{k}(n)$ or $G={L}_{k}(n).$

We define

$\displaystyle\mathcal{M}_{1}(n,k)$ $\displaystyle=$
$\displaystyle\left\\{G\subseteq{M}_{k}(n)-E^{\prime},\mbox{where
$E^{\prime}\subset E_{1}({M}_{k}(n))$ with
$|E^{\prime}|\leq\lfloor\frac{k^{2}}{4}\rfloor$}\right\\},$
$\displaystyle\mathcal{L}_{1}(n,k)$ $\displaystyle=$
$\displaystyle\left\\{G\subseteq{L}_{k}(n)-E^{\prime},\mbox{where
$E^{\prime}\subset E_{1}({L}_{k}(n))$ with
$|E^{\prime}|\leq\lfloor\frac{k^{2}}{4}\rfloor$}\right\\}.$

Li, Liu and Peng [19] recently obtained the $Q$-index counterpart of Theorem
1.2.

###### Theorem 1.3

Let $k>1,$ $n\geq k^{4}+k^{3}+4k^{2}+k+6.$ Let $G$ be a connected graph with
$n$ vertices and minimum degree $\delta(G)\geq k$. If

$q(G)\geq 2(n-k-1),$

then $G$ has a Hamilton cycle unless $G\in\mathcal{M}_{1}(n,k)$ or
$G\in\mathcal{L}_{1}(n,k).$

For convenience, for the rest of this paper, we denote

${A}(n,k,\delta):=K_{k-1}\vee(K_{\delta-k+2}\cup{K_{n-\delta-1}}).$

Obviously, for any integers $k>1,\delta\geq 1$ and $n>\delta+1,$
${A}(n,k,\delta)$ is not $k$-connected. For the graph ${A}(n,k,\delta),$ let

$X:=\\{v\in V({A}(n,k,\delta)):d(v)=\delta\\},\qquad Y:=\\{v\in
V({A}(n,k,\delta)):d(v)=n-1\\},$ $Z:=\\{v\in
V({A}(n,k,\delta)):d(v)=n-\delta+k-3\\}.$

Let $E^{\prime}$ denote the edge set of $E({A}(n,k,\delta))$ whose endpoints
are both from $Y\cup Z.$ We define

$\mathcal{A}_{1}(n,k,\delta):\\\
=\left\\{G\subseteq{A}(n,k,\delta)-E^{\prime},\mbox{where $E^{\prime}\subset
E({A}(n,k,\delta))$ with
$|E^{\prime}|\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor$}\right\\},$
$\mathcal{A}_{2}(n,k,\delta):=\left\\{G\subseteq{A}(n,k,\delta)-E^{\prime},\mbox{where
$E^{\prime}\subset E({A}(n,k,\delta))$ with
$|E^{\prime}|=\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1$}\right\\},$
$F(k,\delta):=(k^{2}+2k-3)\delta^{2}-(2k^{3}-k^{2}-17k+8)\delta+k^{4}-3k^{3}-8k^{2}+23k+4.$

In [8], using the adjacency spectral radius, it is obtained that

###### Theorem 1.4

Let $\delta\geq k\geq 3,n\geq(\delta-k+2)(k^{2}-2k+4)+3.$ Let $G$ be a
connected graph of order $n$ and minimum degree $\delta(G)\geq\delta$. If

$\lambda(G)\geq n-\delta+k-3,$

then $G$ is $k$-connected unless $G={A}(n,k,\delta)$.

Motivated by Theorem 1.3, as the $Q$-spectral counterpart of Theorem 1.4, we
have the following main result of this paper.

###### Theorem 1.5

Let $G$ be a connected graph of order $n$ with minimum degree
$\delta(G)=\delta\geq k\geq 3.$ If $n\geq F(k,\delta)$and

$q(G)\geq 2(n-\delta+k-3),$

then $G$ is $k$-connected unless $G\in\mathcal{A}_{1}(n,k,\delta)$.

##  2 Preliminaries

In this section, we present some basic notations and lemmas.

Let $x=(x_{1},x_{2},...,x_{n})^{T}\neq 0,$ by Rayleigh’s principle, we have

$q(G)=\max_{x}\frac{\langle Q(G)x,x\rangle}{\langle
x,x\rangle}=\max_{x}\frac{x^{T}Q(G)x}{x^{T}x}.$

By the definition of $Q(G),$ we have

$\langle Q(G)x,x\rangle=\sum_{i\sim j}(x_{i}+x_{j})^{2}.$

If $z$ is the corresponding unit positive eigenvector (usually called Perron
vector) of $q(G),$ then

$Q(G)z=q(G)z.$

According to the Perron-Frobenius theorem, we have $x_{i}>0$ for each $i\in
V(G)$ if $G$ is connected. Taking the $i$-th entry of both sides and
rearranging terms, we have

$\displaystyle(q(G)-d(i))z_{i}=\sum_{i\sim j}z_{j}.$ (1)

Let $N(i)$ denote the set of neighbours of $i,$ $N[i]=N(i)\cup\\{i\\}$. From
the above, we have the following lemma.

###### Lemma 2.1

[19] For any $i,j\in V(G),$ we have

$\displaystyle(q(G)-d(i))(z_{i}-z_{j})=(d(i)-d(j))z_{j}+\sum_{k\in
N(i)\setminus N(j)}z_{k}-\sum_{l\in N(j)\setminus N(i)}z_{l}.$ (2)

###### Lemma 2.2

[10] Let $G$ be a graph of order $n.$ Then

$q(G)\leq\frac{2m}{n-1}+n-2.$

Using the ideas in [14], we obtain

###### Lemma 2.3

Let $G$ be a connected graph of order $n\geq 2\delta-k+5,$ size $m,$ minimum
degree $\delta(G)=\delta\geq k\geq 2.$ If

$m>\frac{1}{2}n(n-1)-(\delta-k+3)(n-\delta-2),$

then $G$ is $k$-connected unless $G$ is a subgraph of ${A}(n,k,\delta).$

Proof. Suppose on the contrary that $G$ is not $k$-connected. Let $X$ be a
minimum vertex-cut with $1\leq|X|\leq k-1.$ Assume that
$C_{1},C_{2},...,C_{t}$ $(t>1)$ are the components of $G-X,$ where
$|C_{1}|\leq|C_{2}|\leq...\leq|C_{t}|.$ Clearly, for $1\leq i\leq t,$ each
vertex in $C_{i}$ is adjacent to at most $|C_{i}|-1$ vertices of $C_{i}$ and
$|X|$ vertices of $X.$ Thus

$\delta|C_{i}|\leq\sum_{x\in C_{i}}d(x)\leq(|C_{i}|-1+|X|)|C_{i}|,$

hence $|C_{i}|\geq\delta-|X|+1,$ and therefore $\delta-|X|+1\leq|C_{i}|\leq
n-|X|-(\delta-|X|+1),$ which implies

$\displaystyle\delta-|X|+1\leq|C_{i}|\leq n-\delta-1.$

Let $S=\cup_{i=2}^{t}C_{i}.$ Then from above, $\delta-|X|+1\leq|S|\leq
n-\delta-1.$ Since $G-X$ is disconnected, there are no edges between $C_{1}$
and $S$ in $G,$ we obtain

$m\leq\frac{1}{2}n(n-1)-|C_{1}||S|.$

In order to prove that $G$ is a subgraph of ${A}(n,k,\delta),$ it suffices to
show that $|C_{1}|=\delta-k+2.$

If $|C_{1}|\geq\delta-k+3,$ as $|C_{1}|\leq|C_{2}|\leq...\leq|C_{t}|$ and
$S=\cup_{i=2}^{t}C_{i},$ we have $|C_{1}|\leq\frac{n-|X|}{2}.$ Therefore for
$\delta-k+3\leq|C_{1}|\leq\frac{n-|X|}{2},$ we have
$|C_{1}||S|=|C_{1}|(n-|X|-|C_{1}|)\geq(\delta-k+3)(n-|X|-(\delta-k+3))$, the
equality is attained when $|C_{1}|=\delta-k+3.$ Since $|X|\leq k-1,$

$\displaystyle m$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}n(n-1)-|C_{1}||S|$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}n(n-1)-(\delta-k+3)(n-|X|-(\delta-k+3))$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}n(n-1)-(\delta-k+3)(n-\delta-2).$

From the assumption, we get a contradiction. Thus $|C_{1}|\leq\delta-k+2.$
Combining this with $|C_{1}|\geq\delta-|X|+1\geq\delta-k+2,$ we have
$|C_{1}|=\delta-k+2.$

Hence, as the minimum degree of $G$ is $\delta$, we have $|X|=k-1$ and
$d_{G}(i)=\delta$ for each $i\in C_{1},$ therefore each vertex of $C_{1}$ is
adjacent to each vertex of $X.$ We obtain the result.

##  3 Proof of the Main Result

To prove Theorem 1.5, we still need to prove the following several lemmas.

###### Lemma 3.1

Assume $\delta\geq k\geq 3,$ let $G$ be a connected graph of order $n\geq
F(k,\delta)$ and minimum degree $\delta\geq k.$ For each graph
$G\in\mathcal{A}_{1}(n,k,\delta),$ we have $q(G)\geq 2(n-\delta+k-3).$

Proof. Let $G$ be a graph in $\mathcal{A}_{1}(n,k,\delta).$ We easily get that
$q(K_{n-\delta+k-2}\cup\overline{K_{\delta-k+2}})=2(n-\delta+k-3)$. Now we
construct a vector $z,$ where $z_{i}=1$ if $i\in Y\cup Z,$ $z_{j}=0$ if $j\in
X.$ Obviously $z$ is the corresponding eigenvector to
$q(K_{n-\delta+k-2}\cup\overline{K_{\delta-k+2}}).$ Then we obtain

$\langle Q(G)z,z\rangle-\langle
Q(K_{n-\delta+k-2}\cup\overline{K_{\delta-k+2}})z,z\rangle=(\delta-k+2)(k-1)-4|E^{\prime}|\geq
0.$

By the Rayleigh’s principle, we have $q(G)\geq 2(n-\delta+k-3).$

###### Lemma 3.2

Assume $\delta\geq k\geq 3,$ let $G$ be a connected graph of order $n\geq
F(k,\delta)$ and minimum degree $\delta\geq k.$ For each graph
$G\in\mathcal{A}_{2}(n,k,\delta),$ we have $q(G)>2(n-\delta+k-3)-1.$

Proof. Let $z$ be the vector defined in Lemma 3.1. We have

$\langle Q(G)z,z\rangle-\langle
Q(K_{n-\delta+k-2}\cup\overline{K_{\delta-k+2}})z,z\rangle=(\delta-k+2)(k-1)-4|E^{\prime}|\geq-4.$

Similarly, we have $q(G)\geq
2(n-\delta+k-3)-\frac{4}{\|z\|^{2}}>2(n-\delta+k-3)-1.$

We put our attention to prove $q(G)<2(n-\delta+k-3)$ for
$G\in\mathcal{A}_{2}(n,k,\delta)$ in the following.

Let $G$ be a graph among $\mathcal{A}_{2}(n,k,\delta)$ with the largest
$Q$-index, assume further that the induced subgraph $G[Y]$ contains the
largest number of edges. Then $|Y|=k-1\geq 2,$ i.e., $k\geq 3.$

In the following, let $x$ be the eigenvector corresponding to $q(G).$ Moreover
we may assume $\max\limits_{i\in V(G)}x_{i}=1.$ Following this, we have

###### Lemma 3.3

Assume $G\in\mathcal{A}_{2}(n,k,\delta)$ as defined above. For each $i\in X,$
we have

$x_{i}\leq\frac{k-1}{q(G)-(2\delta-k+1)}.$

Proof. Using equation (1) at vertex $i,$ we have

$(q(G)-d(i))x_{i}=\sum_{j\in X\setminus i}x_{j}+\sum_{j\in Y}x_{j}.$

As $d(i)=\delta,$ $x_{i}$ is the same for all vertex in $X,$ and
$\max\limits_{i\in V(G)}x_{i}=1$, we have

$\left(q(G)-\big{(}\delta+(\delta-k+1)\big{)}\right)x_{i}=\sum_{j\in Y}x_{j}.$

The proof is completed.

Now we divide $Y,Z$ into the following two parts, respectively.

$Y_{1}=\\{i\in Y:d(i)=n-1\\},\quad Y_{2}=\\{i\in Y:d(i)\leq n-2\\},$
$Z_{1}=\\{i\in Z:d(i)=n-\delta+k-3\\},\quad Z_{2}=\\{i\in Z:d(i)\leq
n-\delta+k-4\\}.$

We first declare the following truth: $Z_{1}\neq\emptyset$ since
$n-\delta-1>2\left(\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1\right)+1,$
and $n\geq F(k,\delta).$

We already know the upper bound of $x_{i}$ for each $i\in X$ and $x_{i}<1.$
Clearly $\max\limits_{i\in V(G)}x_{i}=\max\limits_{i\in Y\cup Z}x_{i}.$

We also need the following several lemmas.

###### Lemma 3.4

Let $G\in\mathcal{A}_{2}(n,k,\delta)$ as above. If $Y_{2}\neq\emptyset,$ then
we have $x_{i}>x_{j}$ for all $i\in Z_{1}$ and $j\in Y_{2}.$

Proof. By contradiction, assume that there exist some $i\in Z_{1}$ and $j\in
Y_{2}$ such that $x_{i}\leq x_{j}.$ For $k\in Y$ and $j\nsim k,$ we define a
new graph $G^{\prime}\in\mathcal{A}_{2}(n,k,\delta)$ by removing the edge $ik$
and adding a new edge $jk.$ Since

$\langle Q(G^{\prime})x,x\rangle-\langle
Q(G)x,x\rangle=(x_{j}-x_{i})(x_{i}+x_{j}+2x_{k})\geq 0,$

we get $q(G^{\prime})\geq q(G)$ and the induced graph $G^{\prime}[Y]$ has more
edges than $G[Y],$ which contradicts the choice of $G.$ The result follows.

###### Lemma 3.5

Assume $G\in\mathcal{A}_{2}(n,k,\delta)$ as defined above.

  1. (1)

If $Z_{2}\neq\emptyset,$ then we have $x_{i}>x_{j}$ for all $i\in Z_{1}$ and
$j\in Z_{2}.$

  2. (2)

If $Y_{1},Y_{2}\neq\emptyset,$ then we have $x_{i}>x_{j}$ for any $i\in Y_{1}$
and $j\in Y_{2}.$

  3. (3)

If $Y_{1}\neq\emptyset,$ then we have $x_{i}>x_{j}$ for any $i\in Y_{1}$ and
$j\in Z_{1}.$

Proof. (1). Using Lemma 2.1, we have

$(q(G)-d(i))(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus
N(j)}x_{k}-\sum_{l\in N(j)\setminus N(i)}x_{l}.$

For each $i\in Z_{1}$ and $j\in Z_{2},$ note that $N(j)\setminus\\{i\\}\subset
N(i)\setminus\\{j\\}.$ Rearranging the last equation, we obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in
N(i)\setminus N[j]}x_{k}.$ (3)

As $d(i)>d(j),$ the proof is completed.

(2). If $Y_{1},Y_{2}\neq\emptyset,$ using Lemma 2.1, we have

$(q(G)-d(i))(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus
N(j)}x_{k}-\sum_{l\in N(j)\setminus N(i)}x_{l}.$

For each $i\in Y_{1}$ and $j\in Y_{2},$ note that $N(j)\setminus\\{i\\}\subset
N(i)\setminus\\{j\\}.$ Rearranging the last equation, we obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in
N(i)\setminus N[j]}x_{k}.$

as $d(i)>d(j),$ the proof is completed.

(3). If $Y_{1}\neq\emptyset,$ applying Lemma 2.1, we have

$(q(G)-d(i))(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus
N(j)}x_{k}-\sum_{l\in N(j)\setminus N(i)}x_{l}.$

For each $i\in Y_{1}$ and $j\in Z_{1},$ note that $N(j)\setminus\\{i\\}\subset
N(i)\setminus\\{j\\}.$ Rearranging the last equation, we obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})=(d(i)-d(j))x_{j}+\sum_{k\in
N(i)\setminus N[j]}x_{k}.$

as $d(i)>d(j),$ the proof is completed.

From above, bearing in mind that $Z_{1}\neq\emptyset,$ we have

  1. (1)

If $Y_{1}=\emptyset,$ obviously we have $Y_{2}\neq\emptyset$ since $G$ is a
connected graph. We divide it into two subcases:

If $Z_{2}=\emptyset$, from above we know $Z_{1}\neq\emptyset.$ We easily have
that $\max\limits_{i\in V(G)}x_{i}=\max\limits_{i\in Z_{1}}x_{i}$ from Lemma
3.4;

If $Z_{2}\neq\emptyset$, we already know that $Z_{1}\neq\emptyset,$ so we
still have $\max\limits_{i\in V(G)}x_{i}=\max\limits_{i\in Z_{1}}x_{i}$ from
Lemmas 3.4 and 3.5.

  2. (2)

If $Y_{1}\neq\emptyset,$ we divide it into two subcases:

If $Y_{2}=\emptyset$, we then have $Z_{2}\neq\emptyset$ for
$G\in\mathcal{A}_{2}(n,k,\delta).$ And $Z_{1}\neq\emptyset,$ then we get that
$\max\limits_{i\in V(G)}x_{i}=\max\limits_{i\in Y_{1}}x_{i}$ from Lemma 3.5;

If $Y_{2}\neq\emptyset$, if $Z_{2}=\emptyset,$ we have $\max\limits_{i\in
V(G)}x_{i}=\max\limits_{i\in Y_{1}}x_{i}$ from Lemmas 3.4 and 3.5. If
$Z_{2}\neq\emptyset,$ we still have $\max\limits_{i\in
V(G)}x_{i}=\max\limits_{i\in Y_{1}}x_{i}$ from Lemmas 3.4 and 3.5.

The key step for proving Lemma 3.7 is to show Lemma 3.6.

###### Lemma 3.6

Assume $G\in\mathcal{A}_{2}(n,k,\delta)$ as defined above. We have

$\max\limits_{i\in V(G)}x_{i}-\min\limits_{j\in Y\cup
Z}x_{j}\leq\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

Proof. We distinguish the proof into two cases.

Case 1: $Y_{1}=\emptyset.$ Notice that $\max\limits_{i\in V(G)}x_{i}$ is
attained at the vertices in $Z_{1}$. For each $i\in Z_{1},$
$d(i)=n-\delta+k-3,$ hence the vertex $i$ is adjacent to all other vertices in
$Y\cup Z.$

Subcase 1.1: If $j\in Z_{2},$ we have $N(i)\setminus N[j]=\\{k:k\in Y\cup Z$
and $k\nsim j\\}.$ Thus we have
$d(i)-d(j)\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1$ and
$|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1.$ Note that
$N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\},$ applying equation (3), we
obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})$ $\displaystyle=$
$\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus N[j]}x_{k}$
$\displaystyle\leq$
$\displaystyle\left\lfloor\frac{(\delta-k+2)(k-1)}{2}\right\rfloor+2.$

Since $i\in Z_{1},\delta\geq k,$ we have

$x_{i}-x_{j}\leq\frac{\frac{(\delta-k+2)(k-1)}{2}+2}{q(G)-(n-\delta+k-3)+1}=\frac{(\delta-k+2)(k-1)+4}{2(q(G)-n+\delta-k+4)}<\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

Subcase 1.2: If $j\in Y_{2},$ we have $N(i)\setminus(N[j])=\\{k:k\in Y\cup Z$
and $k\nsim j\\},$ and $N(j)\setminus N[i]=X.$ Thus $|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1.$ Meanwhile,
note that
$|d(i)-d(j)|\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+\delta-k+3.$
Similarly, we obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})$ $\displaystyle=$
$\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus N[j]}x_{k}-\sum_{l\in
X}x_{l}$ $\displaystyle\leq$ $\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in
N(i)\setminus N[j]}x_{k}$ $\displaystyle\leq$
$\displaystyle\frac{(\delta-k+2)(k-1)}{2}+\delta-k+2+2$ $\displaystyle=$
$\displaystyle\frac{(\delta-k+2)(k+1)+4}{2}.$

Since $i\in Z_{1},\delta\geq k,$ we easily have

$\displaystyle x_{i}-x_{j}$ $\displaystyle\leq$
$\displaystyle\frac{\frac{(\delta-k+2)(k+1)}{2}+2}{q(G)-(n-\delta+k-3)+1}=\frac{(\delta-k+2)(k+1)+4}{2(q(G)-n+\delta-k+4)}$
$\displaystyle<$ $\displaystyle\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

Case 2: $Y_{1}\neq\emptyset.$ Notice that $\max\limits_{i\in V(G)}x_{i}$ is
attained at the vertices in $Y_{1}$. When $i\in Y_{1},$ $d(i)=n-1,$ hence the
vertex $i$ is adjacent to all other vertices in $V(G).$

Subcase 2.1: If $j\in Y_{2},$ we have $N(i)\setminus N[j]=\\{k:k\in Y\cup
Z\mbox{ and }k\nsim j\\}.$ Thus we have
$d(i)-d(j)\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1$ and
$|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1.$ Note that
$N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\},$ applying equation (3), we
obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})$ $\displaystyle=$
$\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus N[j]}x_{k}$
$\displaystyle\leq$
$\displaystyle\left\lfloor\frac{(\delta-k+2)(k-1)}{2}\right\rfloor+2.$

Since $i\in Y_{1},\delta\geq k,$ we easily have

$\displaystyle x_{i}-x_{j}$ $\displaystyle\leq$
$\displaystyle\frac{\frac{(\delta-k+2)(k-1)}{2}+2}{q(G)-(n-1)+1}=\frac{(\delta-k+2)(k-1)+4}{2(q(G)-n+2)}$
$\displaystyle<$ $\displaystyle\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

Subcase 2.2: If $j\in Z_{1},$ we have $N(i)\setminus N[j]=X-\\{j\\},$ and
$N(j)\setminus N[i]=\emptyset.$ Thus $|N(i)\setminus
N[j]|=(n-1)-(n-\delta+k-3+1)=\delta-k+1.$ Note that $d(i)-d(j)=\delta-k+2$, we
similarly obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})$ $\displaystyle=$
$\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus N[j]}x_{k}$
$\displaystyle\leq$ $\displaystyle\delta-k+2+\delta-k+1$ $\displaystyle<$
$\displaystyle 2(\delta-k+2).$

Since $i\in Y_{1},\delta\geq k,$ we have

$\displaystyle x_{i}-x_{j}<\frac{2(\delta-k+2)}{q(G)-(n-1)+1}$
$\displaystyle<$
$\displaystyle\frac{4(\delta-k+2)}{2(q(G)-n+1)}<\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

Subcase 2.3: If $j\in Z_{2},$ we have $N(i)\setminus N[j]=\\{k:k\in X\cup
Y\cup Z$ and $k\nsim j\\},$ and $N(j)\setminus N[i]=\emptyset.$ Thus we have
$|N(i)\setminus
N[j]|\leq\delta-k+2+\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1.$
Meanwhile, note that
$d(i)-d(j)\leq\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+\delta-k+3.$
Similarly, we obtain

$\displaystyle(q(G)-d(i)+1)(x_{i}-x_{j})$ $\displaystyle=$
$\displaystyle(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus N[j]}x_{k}$
$\displaystyle\leq$ $\displaystyle\frac{(\delta-k+2)(k-1)}{2}+2(\delta-k+2)+2$
$\displaystyle=$ $\displaystyle\frac{(\delta-k+2)(k+3)+4}{2}.$

Since $i\in Y_{1},\delta\geq k,$ we have

$\displaystyle
x_{i}-x_{j}\leq\frac{\frac{(\delta-k+2)(k+3)}{2}+2}{q(G)-(n-1)+1}$
$\displaystyle=$
$\displaystyle\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+2)}<\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}.$

The proof is completed.

Now we can prove Lemma 3.7, which is crucial for Theorem 1.5.

###### Lemma 3.7

Let $G$ be a connected graph of order $n\geq F(k,\delta)$ and minimum degree
$\delta\geq k\geq 3.$ For each graph $G\in\mathcal{A}_{2}(n,k,\delta),$ we
have $q(G)<2(n-\delta+k-3).$

Proof. We assume $G\in\mathcal{A}_{2}(n,k,\delta)$ such that $G$ has the
largest $Q$-index $q(G)$ among $\mathcal{A}_{2}(n,k,\delta)$ and $G[Y]$
contains the largest number of edges. Let $x$ be the eigenvector corresponding
to $q(G),$ and $G^{\prime}[X]$ be the complete graph $K_{\delta-k+2}$ induced
by $X.$ Lemmas 3.3 and 3.6 imply that

$\displaystyle\langle Q(G)x,x\rangle-\langle
Q(\overline{K_{\delta-k+2}}+K_{n-\delta+k-2})x,x\rangle$ $\displaystyle=$
$\displaystyle\sum_{i,j\in E(G^{\prime}[X])}(x_{i}+x_{j})^{2}+\sum_{i\in
X,j\in Y}(x_{i}+x_{j})^{2}-\sum_{{i,j}\in E^{\prime}}(x_{i}+x_{j})^{2}$
$\displaystyle\leq$
$\displaystyle\frac{(\delta-k+2)(\delta-k+1)}{2}\left(2\frac{k-1}{q(G)-(2\delta-k+1)}\right)^{2}$
$\displaystyle+(k-1)(\delta-k+2)\left(1+\frac{k-1}{q(G)-(2\delta-k+1)}\right)^{2}$
$\displaystyle-4|E^{\prime}|\left(1-\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}\right)^{2}.$

As
$|E^{\prime}|=\left\lfloor\frac{(\delta-k+2)(k-1)}{4}\right\rfloor+1\geq\frac{(\delta-k+2)(k-1)+1}{4},$
we have

$\displaystyle\langle Q(G)x,x\rangle-\langle
Q(\overline{K_{\delta-k+2}}+K_{n-\delta+k-2})x,x\rangle$ $\displaystyle\leq$
$\displaystyle\frac{(\delta-k+2)(\delta-k+1)}{2}\left(2\frac{k-1}{q(G)-(2\delta-k+1)}\right)^{2}$
$\displaystyle+(k-1)(\delta-k+2)\left(1+\frac{k-1}{q(G)-(2\delta-k+1)}\right)^{2}$
$\displaystyle-\left((k-1)(\delta-k+2)+1\right)\left(1-\frac{(\delta-k+2)(k+3)+4}{2(q(G)-n+1)}\right)^{2}.$

Since $n\geq F(k,\delta),$ and $q(G)>2(n-\delta+k-3)-1$ by Lemma 3.2, we have

$\langle Q(G)x,x\rangle-\langle
Q(\overline{K_{\delta-k+2}}+K_{n-\delta+k-2})x,x\rangle<0.$

According to the Rayleigh’s principle,

$\frac{\langle
Q(\overline{K_{\delta-k+2}}+K_{n-\delta+k-2})x,x\rangle}{\langle
x,x\rangle}\leq
q(\overline{K_{\delta-k+2}}+K_{n-\delta+k-2})=2(n-\delta+k-3).$

Therefore, we have $q(G)=\frac{\langle Q(G)x,x\rangle}{\langle
x,x\rangle}<2(n-\delta+k-3).$

Now we are ready to prove Theorem 1.5.

Proof. By Lemma 2.2, we have

$2(n-\delta+k-3)\leq q(G)\leq\frac{2m}{n-1}+n-2.$

Therefore

$\displaystyle m$ $\displaystyle\geq$
$\displaystyle\frac{(n-2\delta+2k-4)(n-1)}{2}$ $\displaystyle=$
$\displaystyle\frac{n(n-1)}{2}-(\delta-k+3)(n-\delta-2)+n-\delta-2-(\delta-k+2)(\delta+1)$
$\displaystyle>$ $\displaystyle\frac{n(n-1)}{2}-(\delta-k+3)(n-\delta-2),$

the last inequality holds as $n\geq F(k,\delta).$ By Lemma 2.3, $G$ is
$k$-connected unless $G\in{A}(n,k,\delta).$ Together with Lemmas 3.1 and 3.7,
the result follows.

## References

  * [1] A. Berman, X.D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233–240.
  * [2] B. Bollobas, Extremal Graph Theory, Academic Press, 1978.
  * [3] R.A. Brualdi, E.S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Algebra. Discrete Method 7 (1986), 265–272.
  * [4] S.L. Chandran, Minimum cuts, girth and spectral threshold, Inform. Process. Lett. 89 (3) (2004), 105–110.
  * [5] S.M. Cioabǎ, Eigenvalues and edge-connectivity of regular graphs, Linear Algebra Appl. 432 (2010), 458–470.
  * [6] L.H. Feng, J.X. Cao, W.J. Liu, S.F. Ding, H. Liu, The spectral radius of edge chromatic critical graphs, Linear Algebra Appl. 492 (2016), 78–88.
  * [7] L.H. Feng, P.L. Zhang, H. Liu, W.J. Liu, M.M. Liu, Y.Q. Hu, Spectral conditions for some graphical properties, Linear Algebra Appl. 524 (2017), 182–198.
  * [8] L.H. Feng, P.L. Zhang, W.J. Liu, Spectral radius and $k$-connectedness of graphs, Monatsh. Math. 185 (2018), 651–661.
  * [9] L.H. Feng, X.M. Zhu, W.J. Liu, Wiener index, Harary index and graph properties, Discrete Appl. Math. 223 (2017), 72–83.
  * [10] L.H. Feng, G.H. Yu, On the three conjectures involving the signless Laplacian spectral radius of graphs, Publ. Inst. Math. (Beograd) 85 (99) (2009), 35–38.
  * [11] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (98) (1973), 298–305.
  * [12] M. Fiedler, V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl. 432 (9) (2010), 2170–2173.
  * [13] X.F. Gu, H.-J. Lai, P. Li, S.M. Yao, Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs, J. Graph Theory 81 (1) (2016), 16–29.
  * [14] Z.M. Hong, Z.J. Xia, F. Chen, L.Volkmann, Sufficient conditions for graphs to be $k$-connected, maximally connected and super-connected, Complexity, (2021), 1–11.
  * [15] B.F. Huo, X.L. Li, Y.T. Shi, Complete solution to a conjecture on the maximal energy of unicyclic graphs, European J. Combin. 32(5) (2011), 662–673.
  * [16] B.L. Li, B. Ning, Spectral analogues of Erdős’s and Moon-Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra 64 (11)(2016), 2252–2269.
  * [17] J. Li, X.L. Li, Y.T. Shi, On the maximal energy tree with two maximum degree vertices, Linear Algebra Appl. 435(9) (2011), 2272–2284.
  * [18] X.L. Li, Y.T. Shi, M.Q. Wei, J. Li, On a conjecture about tricyclic graphs with maximal energy, MATCH Commun. Math. Comput. Chem. 72 (1) (2014), 183–214.
  * [19] Y.W. Li, Y. Liu, X. Peng, Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree, Linear Multilinear Algebra. 66 (10) (2018), 2011-2023.
  * [20] H.Q. Liu, M. Lu, F. Tian, Edge-connectivity and (signless) Laplacian eigenvalue of graphs, Linear Algebra Appl. 439 (12)(2013), 3777–3784.
  * [21] H.Q. Liu, M. Lu, F. Tian, On the spectral radius of graphs with cut edges, Linear Algebra Appl. 389 (2004) 139–145.
  * [22] W.J. Liu, M.M. Liu, L.H. Feng, Spectral conditions for graphs to be $\beta$-deficient involving minimum degree, Linear Multilinear Algebra 66 (4) (2018), 792–802.
  * [23] W.J. Liu, M.M. Liu, P.L. Zhang, L.H. Feng, Spectral conditions for graphs to be $k$-hamiltonian or $k$-path-coverable, Discuss. Math. Graph Theory 40 (1) (2020), 161-179.
  * [24] M. Lu, H.Q. Liu, F. Tian, Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (7) (2012), 1670–1674.
  * [25] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (9) (2010), 2243–2256
  * [26] V. Nikiforov, Spectral radius and Hamiltonicity of graphs with large minimum degree, Czechoslovak Math. J. 66 (141)(2016), 925–940.
  * [27] B. Ning, J. Ge, Spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra 63 (8) (2015), 1520–1530.
  * [28] S. O, S.M. Cioabǎ, Edge-connectivity, eigenvalues, and matchings in regular graphs, SIAM J. Discrete Math. 24 (4) (2010), 1470–1481.
  * [29] M.J. Zhang, S.C. Li, Extremal Halin graphs with respect to the signless Laplacian spectra, Discrete Appl. Math. 213 (2016), 207–218.
  * [30] M. Zhang, S.C. Li, Extremal cacti of given matching number with respect to the distance spectral radius, Appl. Math. Comput. 291 (2016), 89–97.
  * [31] X.-D. Zhang, The signless Laplacian spectral radius of graphs with given degree sequence, Discrete Appl. Math. 157 (13) (2009), 2928–2937.
  * [32] B. Zhou, Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl. 432 (2/3) (2010), 566–570.
  * [33] Q.N. Zhou, L.G. Wang, Distance signless Laplacian spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra 65 (11) (2017), 2316–2323.
  * [34] Q.N. Zhou, L.G. Wang, Y. Lu, Some sufficient conditions on $k$-connected graphs, Appl. Math. Comput. 325 (2018), 332–339