#  A tight $Q$-index condition for a graph to be $k$-path-coverable involving
minimum degree††thanks: This research was supported by NSFC (Nos. 11871479,
12071484), Hunan Provincial Natural Science Foundation (2020JJ4675,
2018JJ2479). E-mail addresses: taocheng@sdnu.edu.cn(Tao Cheng),
fenglh@163.com(L. Feng), ytli0921@hnu.edu.cn(Y. Li), wjliu6210@126.com(W.
Liu).

Tao Chenga, Lihua Fengb, Yongtao Lic, Weijun Liub
a School of Mathematics and Statistics, Shandong Normal University
Jinan, Shandong, 250014, P.R. China.
bSchool of Mathematics and Statistics, Central South University
New Campus, Changsha, Hunan, 410083, P.R. China.
cSchool of Mathematics, Hunan University
Changsha, Hunan, 410082, P.R. China

(April 26, 2020)

###### Abstract

A graph $G$ is $k$-path-coverable if its vertex set $V(G)$ can be covered by
$k$ or fewer vertex disjoint paths. In this paper, using the $Q$-index of a
connected graph $G$, we present a tight sufficient condition for $G$ with
fixed minimum degree and large order to be $k$-path-coverable.

Key words: $Q$-index; minimum degree; $k$-path-coverable.

##  1 Introduction

We only consider simple connected graphs throughout paper. The notations we
used are standard from [2]. 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)|=e(G)$. We use
$d(v)$ to denote the degree of a vertex $v$ in $G$, and the minimum degree is
$\delta(G)=\delta$. For two vertex-disjoint graphs $G$ and $H,$ $G\cup H$ is
denoted to be the disjoint union of $G$ and $H,$ $G\vee H$ the join of $G$ and
$H,$ which is obtained from $G\cup H$ by adding all possible edges between $G$
and $H.$ We use the symbol $i\sim j$ to denote the vertices $i$ and $j$ are
adjacent, and $i\nsim j$ otherwise.

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}$ with diagonal entry
$d_{ii}=d(i)$. The _signless Laplacian matrix_ $Q(G)$ of $G$ is $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$.

For people that working on spectral graph theory, 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 many classes of graphs, such as graphs with given diameter
[13], edge chromatic number [8], domination number [30]. For the $Q$-index
counterpart of the above problem, Zhang [33] gave the $Q$-index of graphs with
given degree sequence, Zhou [35] 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 [14,
17, 18, 32, 34].

Analogous to the Brualdi–Solheid problem, the following problem regarding the
adjacency spectral radius was proposed in [26]: What is the maximum spectral
radius of a graph $G$ on $n$ vertices without a subgraph isomorphic to a given
graph $F$? For this problem, Fiedler and Nikiforov [12] obtained tight
sufficient conditions for graphs to be hamiltonian or traceable. This
motivates further study for such question, see [10, 9, 12, 37, 21, 24, 25, 35,
22, 36, 28].

When the minimum degree is involved in contrast with the results in [12],
using the adjacency spectral radius, Li and Ning [15] obtained

###### Theorem 1.1

[15] Let $t\geq 1$, and $G$ be a graph of order $n$ with minimum degree
$\delta(G)\geq t$. If $n\geq\max\\{6t+10,(t^{2}+7t+8)/2\\}$ and

$\lambda(G)\geq\lambda(K_{t}\vee(K_{n-2t-1}\cup(t+1)K_{1})),$

then $G$ is traceable, unless $G=K_{t}\vee(K_{n-2t-1}\cup(t+1)K_{1})$.

Theorem 1.1 is generalized by Nikiforov as

###### Theorem 1.2

[27] Let $t\geq 1$ and $G$ be a graph of order $n$. If $n\geq
t^{3}+t^{2}+2t+5$, $\delta(G)\geq t$ and

$\lambda(G)\geq n-t-2,$

then $G$ is traceable unless $G=K_{t+1}\cup K_{n-t-1}$ or
$G=K_{t}\vee(K_{n-2t-1}\cup(t+1)K_{1})$.

In this paper, we consider the $k$-path-coverable problem. A graph $G$ is
$k$-path-coverable if $V(G)$ can be covered by $k$ or fewer vertex-disjoint
paths. In particular, 1-path-coverable is the same as traceable. The disjoint
path cover problem is strongly related to the well-known hamiltonian problem
(one may refer to [16] for a survey), which is among the most fundamental ones
in graph theory, and attracts much attention in theoretical computer science.
However, this problem is NP-complete [29], therefore, finding their guaranteed
sufficient conditions becomes an interesting work. In [19], such Ore-type
condition is obtained.

For convenience, we denote

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

In [24], by generalizing the results in Theorem 1.1 and Theorem 1.2, Liu et.
al. obtained the following sufficient by using the adjacency spectral radius.

###### Theorem 1.3

[24] Let $k\geq 1$ and $\delta\geq 2$. If $G$ is a connected graph on
$n\geq\max\\{\delta^{2}(\delta+k)+\delta+k+5,5k+6\delta+6\\}$ vertices and
minimum degree $\delta(G)\geq\delta$ such that

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

then $G$ is $k$-path-coverable unless $G=B(n,k,\delta)$.

In this paper, we will consider the $Q$-index version of Theorem 1.3. For the
graph ${B}(n,k,\delta)$, let

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

We denote by $E_{1}$ the edge set of $E({R}(n,k,\delta))$ whose endpoints are
both from $Y\cup Z.$ We define

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

Here, the symbol $G\subseteq{R}(n,k,\delta)-E^{\prime}$ means $G$ is a
subgraph of ${R}(n,k,\delta)-E^{\prime}$.

The main result of this paper is

###### Theorem 1.4

Let $k\geq 1$ and $\delta\geq 2$. If $G$ is a connected graph on
$n\geq(\delta^{2}+k\delta+7\delta+6k+9)(\delta^{2}+k\delta+1)$ vertices and
minimum degree $\delta(G)\geq\delta$ such that

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

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

##  2 Preliminary Results

We first present some basic notations and results. For
$x=(x_{1},x_{2},...,x_{n})^{T}\neq 0$, according to the 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\in V(G)}d(i)x_{i}^{2}+2\sum_{i\sim
j}x_{i}x_{j}=\sum_{i\sim j}(x_{i}+x_{j})^{2}.$

If ${h}$ is the unit positive eigenvector of $q(G)$, then

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

If we take the $i$-th entry of both sides and rearranging terms, we get

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

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

###### Lemma 2.1

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

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

We now present some graph notations we will use. The concept of stability was
introduced by Bondy and Chvátal [1]. Let $P$ be a property defined on all
graphs of order $n$. Let $k$ be a non-negative integer. The property $P$ is
said to be $k$-stable if whenever $G+uv$ has property $P$ and

$d_{G}(u)+d_{G}(v)\geq k,$

where $un\notin E(G)$, then $G$ itself has property $P$. Among all the graphs
$H$ of order $n$ such that $G\subseteq H$ and

$d_{H}(u)+d_{H}(v)<k$

for all $uv\notin E(H)$, there is a unique smallest on with respect to size.
We shall call this graph the $k$-closure of G, and denote it by
$\mathrm{cl}_{k}(G)$. Obviously, $\mathrm{cl}_{k}(G)$ can be obtained from $G$
by recursive procedure which consists of joining non-adjacent vertices with
degree-sum at least $k$. This concept plays a prominent role in any structual
graph theory problems.

###### Lemma 2.2

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

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

###### Lemma 2.3

[1] The property that “ $G$ is $k$-path-coverable” is $(n-k)$-stable.

##  3 Proof of the Main Results

In order to prove our main result, we need the following stability result.

###### Lemma 3.1

Let $G$ be a graph of order $n\geq 8\delta+6k+7$, where $k\geq 1$. If
$\delta(G)\geq\delta\geq 1$ and

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

then $G$ is $k$-path-coverable unless $G\subseteq B(n,k,\delta)$.

Proof. Let $G^{\prime}=\mathrm{cl}_{n-k}(G)$. If $G^{\prime}$ is $k$-path-
coverable, then so is $G$ by the $(n-k)$-stablity of $k$-path-coverable. We
now assume that $G^{\prime}$ is not $k$-path-coverable, note that
$\delta(G^{\prime})\geq\delta(G)\geq\delta$ and $e(G^{\prime})\geq e(G)$.
Next, we show that

$\omega(G^{\prime})=n-\delta-k.$

Let $C$ be the vertex set of a maximum clique of $G^{\prime}$, since every two
vertices whose degree sum is at least $n-k$ are adjacent, then $C$ contains
all vertices whose degree is at least $(n-k)/2$. Let $H=G^{\prime}-C$ and
$t=|C|$.

Suppose first that $1\leq t\leq(n+k)/3+\delta+4/3$, observe that
$d_{G^{\prime}}(v)\leq(n-k-1)/2$ for every $v\in V(H)$, if otherwise, we may
assume $d_{G^{\prime}}(v)>(n-k-1)/2$, because $d_{G^{\prime}}(v)$ is a
positive integer, then $d_{G^{\prime}}(v)\geq(n-k-1)/2+1/2=(n-k)/2$, so $v$ is
contained in $C$, a contradiction. Clearly, $d_{C}(v)\leq t-1$, so some
tedious manipulation yields that

$\displaystyle e(G^{\prime})$ $\displaystyle=e(G^{\prime}[C])+e(H)+e(V(H),C)$
$\displaystyle=e(G^{\prime}[C])+\frac{1}{2}\left(\sum\limits_{v\in
V(H)}d_{G^{\prime}}(v)+\sum\limits_{v\in V(H)}d_{C}(v)\right)$
$\displaystyle\leq{t\choose
2}+\frac{1}{2}(n-t)\left(\frac{n-k-1}{2}+t-1\right)$
$\displaystyle=\frac{n+k+1}{4}t+\frac{n(n-k-3)}{4}$
$\displaystyle\leq\frac{n+k+1}{4}\left(\frac{n+k}{3}+\delta+\frac{4}{3}\right)+\frac{n(n-k-3)}{4}$
$\displaystyle=\frac{1}{3}n^{2}+\frac{3\delta-k-4}{12}n+(k+1)(3\delta-k+3)$
$\displaystyle\leq\frac{1}{2}(n-k-\delta-1)(n-k-\delta-2)+(\delta+1)(\delta+k+1),$

which leads to a contradiction (The last inequality follows due to $n\geq
8\delta+6k+7$).

Suppose second that $(n+k)/3+\delta+4/3<t\leq n-\delta-k-1$, note that
$d_{G^{\prime}}(v)\leq n-k-t$ for every $v\in V(H)$, if otherwise, we assume
$d_{G^{\prime}}(v)\geq n-k-t+1$, then $v$ will be adjacent to every vertex in
$C$. Therefore

$\displaystyle e(G^{\prime})$ $\displaystyle=e(G^{\prime}[C])+e(H)+e(V(H),C)$
$\displaystyle\leq e(G^{\prime}[C])+\sum\limits_{v\in V(H)}d_{G^{\prime}}(v)$
$\displaystyle\leq{t\choose 2}+(n-t)(n-k-t)$
$\displaystyle=\frac{3}{2}t^{2}+(-2n+k-\frac{1}{2})t+n(n-k)$
$\displaystyle\leq\frac{3}{2}\left(n-\delta-k-1\right)^{2}+(-2n+k-\frac{1}{2})(n-\delta-k-1)+n(n-k)$
$\displaystyle=\frac{1}{2}(n-k-\delta-1)(n-k-\delta-2)+(\delta+1)(\delta+k+1),$

also a contradiction.

Finally, suppose that $t\geq n-\delta-k+1$, since $G^{\prime}$ is not a
clique, then $V(H)$ is not empty. Note that $d_{G^{\prime}}(v)\geq\delta$ for
every $v\in V(H)$ and $d_{G^{\prime}}(u)\geq t-1\geq n-k-\delta$ for every
$u\in C$, this means that every vertex of $V(H)$ is adjacent to every vertex
of $C$, this contradicts the fact that $C$ is a maximum clique. Consequently,
we now infer that $\omega(G^{\prime})=n-\delta-k$.

We call that a vertex in $C$ is a frontier vertex if it has degree at least
$n-\delta-k$ in $G^{\prime}$, that is to say, it has at least one neighbour in
$H$, and denote $F=\\{u_{1},u_{2},\ldots,u_{s}\\}$ by the set of frontier
vertices. Since $\omega(G^{\prime})=n-\delta-k$, then $d_{G^{\prime}}(v)\geq
n-\delta-k-1$ for every $v\in C$, we can see by the $(n-k)$-stablity that
every vertex in $H$ has degree exactly $\delta$ in $G^{\prime}$, furthermore,
every vertex in $H$ is adjacent to every frontier vertex in $G^{\prime}$, and
then we have $1\leq s\leq\delta$. Since $C$ is a clique $K_{n-\delta-k}$, then
we can choose a path $P$ in $C-F$ with two end-vertices $u_{1}$ and $u_{s}$.

We assert that $s=\delta$.

If $s=1$, then every vertex in $H$ has degree $\delta-1$ in $H$. According to
Dirac’s theorem, $H$ has a path of order at least $\delta$. First, we assume
that $H$ has a path $P^{\prime}$ of order $\delta+1$, and let $x,x^{\prime}$
be the two end-vertices of $P^{\prime}$, then $G^{\prime}$ can be covered by
one path $x^{\prime}P^{\prime}xu_{1}P$ and the rest $(k-1)$ vertices in $H$,
so $G^{\prime}$ is $k$-path-coverable, a contradiction. We now assume that $H$
has no paths of order more than $\delta$, let $P^{\prime}$ be a path of order
$\delta$ in $H$ and $V(H-P^{\prime})=\\{v_{1},v_{2},\ldots,v_{k}\\}$. Observe
that $x$ has no neighbour in $V(H-P^{\prime})$ and $d_{H}(x)=\delta-1$, which
implies that $xx^{\prime}\in E(H)$. Since $H$ has no paths of order more than
$\delta$, then every vertex in $V(H-P^{\prime})$ has no neighbour in
$P^{\prime}$, so $H-P^{\prime}$ has an edge, say, $v_{1}v_{2}$. Then
$G^{\prime}$ can be covered by two paths
$x^{\prime}P^{\prime}xu_{1}P,v_{1}v_{2}$ and the rest $(k-2)$ vertices in $H$,
Also a contradiction.

If $2\leq s\leq\delta-1$, so every vertex in $H$ has degree $\delta-s$ in $H$.
By Dirac’s theorem, $H$ has a path of order at least $\delta-s+1$. We first
assume that $H$ has a path $P^{\prime}$ of order $\delta-s+2$ and
$V(H-P^{\prime})=\\{v_{1},v_{2},\ldots,v_{s+k-2}\\}$, then
$v_{1}u_{1}v_{2}u_{2}\cdots v_{s-1}u_{s-1}x^{\prime}P^{\prime}xu_{s}P$ is path
of order $n-(k-1)$, so $G^{\prime}$ is $k$-path-coverable, a contradiction.
Now we assume that $H$ has no paths of order more than $\delta-s+1$, let
$P^{\prime}$ be a path of order $\delta-s+1$ in $H$ and
$V(H-P^{\prime})=\\{v_{1},v_{2},\ldots,v_{k+s-1}\\}$. Observe that $x$ has no
neighbour in $V(H-P^{\prime})$ and $d_{H}(x)=\delta-s$, which implies that
$xx^{\prime}\in E(H)$. Since $H$ has no paths of order more than $\delta-s-1$,
then every vertex in $V(H-P^{\prime})$ has no neighbour in $P^{\prime}$, so
$H-P^{\prime}$ has an edge, say, $v_{1}v_{2}$. Then
$v_{s}u_{1}v_{1}v_{2}u_{2}v_{3}u_{3}\cdots
v_{s-1}u_{s-1}x^{\prime}P^{\prime}xu_{s}P$ is a path of order $n-(k-1)$, so
$G^{\prime}$ is $k$-path-coverable, this also leads to a contradiction.

We have thus proved that $s=\delta$, as we claimed. Then $H$ is an independent
vertices $\overline{K_{\delta+k}}$, i.e., $G^{\prime}=B(n,k,\delta)$, we have
$G\subseteq B(n,k,\delta)$. The proof is now complete.

###### Lemma 3.2

For each graph $G\in\mathcal{B}_{1}(n,k,\delta)$, we have $q(G)\geq
2(n-k-\delta-1)$.

Proof. Let $G\in\mathcal{B}_{1}(n,k,\delta).$ Note that
$q(K_{n-k-\delta}\cup\overline{K_{\delta+k}})=2(n-k-\delta-1)$, and we define
a characteristic vector $x$, where $x_{i}=1$ if $i\in Y\cup Z$ and $x_{j}=0$
if $j\in X$. Obviously $x$ is the eigenvector corresponding to
$q(K_{n-k-\delta-1}\cup\overline{K_{\delta+k+1}})$. Then we get

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

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

###### Lemma 3.3

For each graph $G\in\mathcal{B}_{2}(n,k,\delta)$, we have
$q(G)>2(n-k-\delta-1)-1.$

Proof. Let $x$ be the column vector defined in the proof of Lemma 3.2. We
obtain that

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

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

Let $G$ be a graph of $\mathcal{B}_{2}(n,k,\delta)$ with the largest signless
Laplacian spectral radius, and furthermore we may assume that the induced
graph $G[Y]$ contains the largest number of edges. Let $h$ be the eigenvector
corresponding to $q(G)$. We assume further that $\max_{i\in V(G)}h_{i}=1$ by a
rescaling.

###### Lemma 3.4

Assume $G\in\mathcal{B}_{2}(n,k,\delta)$. For each $i\in X$, we have
$h_{i}\leq\frac{\delta}{q(G)-\delta}$.

Proof. Applying equation (1) at $i\in X$, we have

$(q(G)-d(i))h_{i}=\sum_{j\in Y}h_{j}.$

Since $d(i)=\delta$ and $\max_{i\in V(G)}h_{i}=1$, we have
$(q(G)-\delta)h_{i}\leq\delta$, the proof is completed.

Next, we divide $Y,Z$ into two parts, respectively.

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

Before proving Lemma 3.5, let us make clear the following truth:
$Z_{1}\neq\emptyset$ as
$n\geq(\delta^{2}+k\delta+7\delta+6k+9)(\delta^{2}+k\delta+1)$. We already
know the upper bound of $h_{i}$ for each $i\in X$ and
${\delta}/{(q(G)-\delta)}<1$ when $n>2\delta+k+3/2$. Therefore we get
$\max_{i\in V(G)}h_{i}=\max_{i\in Y\cup Z}h_{i}$. To obtain the difference
between $\max_{i\in V(G)}h_{i}$ and $\min_{i\in Y\cup Z}h_{i}$, we need to
prove the following several results.

###### Lemma 3.5

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

  1. (1)

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

  2. (2)

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

  3. (3)

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

Proof. (1) By contradiction, we assume that there are some $i\in Z_{1}$ and
$j\in Y_{2}$ satisfying $h_{i}\leq h_{j}$. Let $k\in Y$ and $jk\in E(G)$,
define a new graph $G^{\prime}\in\mathcal{B}_{2}(n,k,\delta)$ by removing an
edge $ik$ and adding a new edge $jk$. Since

$\langle Q(G^{\prime})h,h\rangle-\langle
Q(G)h,h\rangle=(h_{j}-h_{i})(h_{i}+h_{j}+2h_{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 proposition is
proved.

(2) By Lemma 2.1, for each $i\in Z_{1}$ and $j\in Z_{2}$, we have

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

We notice that $N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\}$,
equivalently,

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

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

(3) If $Y_{1}\neq\emptyset$. For each $i\in Y_{1}$ and $j\in Z_{1}$, by Lemma
2.1, we have

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

Note that $N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\}$, rearranging the
last equation, we obtain

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

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

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

###### Lemma 3.6

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

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

Proof. We distinguish it into two cases.

Case 1: $Y_{1}\neq\emptyset.$ Notice that $\max_{i\in V(G)}h_{i}$ is attained
by vertices from $Y_{1}$ by the above analysis. Hence $d(i)=n-1$, i.e., the
vertex $i$ is adjacent to all other vertices in $G$.

Subcase 1.1: If $j\in Y_{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)\delta}{4}\right\rfloor+1$ and
$|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1$. Note that
$N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\}$, applying (4), we get

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

Since $i\in Y_{1}$, then

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

Subcase 1.2: If $j\in Z_{1}$, we have $N(i)\setminus N[j]=X$ and
$N(j)\setminus N[i]=\emptyset$. Then $|N(i)\setminus N[j]|=\delta+k+1$.
Meanwhile, note that $d(i)-d(j)=\delta+k+1$. So

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

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

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

Subcase 1.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+\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1$.
Then, note that
$d(i)-d(j)\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1+\delta+k$.
Therefore, we get

$\displaystyle(q(G)-d(i)+1)(h_{i}-h_{j})$
$\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(d(i)-d(j))x_{j}+\sum_{k\in N(i)\setminus
N[j]}x_{k}$ $\displaystyle\leq\frac{(\delta+k)\delta}{2}+2(\delta+k)+2.$
$\displaystyle=\frac{(\delta+k)(\delta+4)}{2}+2.$

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

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

Case 2: $Y_{1}=\emptyset$. Notice that $\max_{i\in V(G)}h_{i}$ is attained by
vertices from $Z_{1}$. And for each $i\in Z_{1},d(i)=n-\delta+k-1$, hence the
vertex $i$ is adjacent to all other vertices in $Y\cup Z$.

Subcase 2.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 get
$d(i)-d(j)\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1$ and
$|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1$. Note that
$N(j)\setminus\\{i\\}\subset N(i)\setminus\\{j\\}$, applying (4), we get

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

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

$\displaystyle
h_{i}-h_{j}\leq\frac{\frac{(\delta+k)\delta}{2}+2}{q(G)-(n-\delta-k-1)+1}=\frac{(\delta+k)\delta+4}{2(q(G)-n+\delta+k+2)}<\frac{(\delta+k)(\delta+4)+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 we have $|N(i)\setminus
N[j]|\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+1$. We also
observe that
$|d(i)-d(j)|\leq\left\lfloor\frac{(\delta+k)\delta}{4}\right\rfloor+\delta+k+1$.
Similarly, we get

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

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

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

The proof is completed.

In order to prove Theorem 1.4, we also need another lemma.

###### Lemma 3.7

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

Proof. We first assume $G\in\mathcal{B}_{2}(n,k,\delta)$ such that $G$ has the
largest signless Laplacian spectral radius and $G[Y]$ contains the largest
number of edges. Let $q(G)$ be the largest eigenvalue of $Q(G)$ and $h$ be the
eigenvector corresponding to $q(G)$. Lemmas 3.4 and 3.6 together with
$|E^{\prime}|=\left\lfloor\frac{\delta(\delta+k)}{4}\right\rfloor\geq\frac{\delta(\delta+k)+1}{4}$
imply that

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

Since $q(G)>2(n-\delta-k-1)-1$ by Lemma 3.3, then we can choose for our
purpose that $n\geq(\delta^{2}+k\delta+7\delta+6k+9)(\delta^{2}+k\delta+1)$,
to make sure the following holds.

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

According to Rayleigh’s principle,

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

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

Now we are ready to prove Theorem 1.4.

Proof. By Lemma 2.2, we have

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

We obtain

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

the last inequality holds as $n\geq\frac{1}{2}(k+\delta+1)(3\delta+k+2)+1$. By
Lemma 3.1, $G$ is $k$-path coverable unless $G\subseteq{B}(n,k,\delta)$.
Together with Lemma 3.2 and Lemma 3.7, the result follows.

## References

  * [1] J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135.
  * [2] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, North-Holland, Amsterdam, 1976.
  * [3] R.A. Brualdi, E.S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Alg. Disc. Meth. 7 (1986) 265–272.
  * [4] L. Chen, J. Liu, Y. Shi, Matching energy of unicyclic and bicyclic graphs with a given diameter, Complexity 21(2) (2015) 224–238.
  * [5] V. Chvátal, On Hamilton’s ideals, J. Combin. Theory Ser. B 12 (1972) 163–168.
  * [6] G. Chartrand, S. Kapoor, D. Lick, $n$-Hamiltonian graphs, J. Combin. Theory 9 (1970) 308–312.
  * [7] L.H. Feng, P.L. Zhang, H. Liu, W. Liu, M. Liu, Y. Hu, Spectral conditions for some graphical properties, Linear Algebra Appl. 524 (2017) 182–198.
  * [8] L.H. Feng, J. Cao, W. Liu, S. Ding, H. Liu, The spectral radius of edge chromatic critical graphs, Linear Algebra Appl. 492 (2016) 78–88.
  * [9] L.H. Feng, P. Zhang, W. Liu, Spectral radius and $k$-connectedness of graphs, Monatsh. Math. 185 (2018) 651–661.
  * [10] L.H. Feng, X. Zhu, W. Liu, Wiener index, Harary index and graph properties, Discrete Applied Math. 223 (2017) 72–83.
  * [11] L.H. Feng, G.H. Yu, On three conjectures involving the signless Laplacian spectral radius of graphs, Publ. Inst. Math. (Beograd). 85 (2009) 35–38.
  * [12] M. Fiedler, V. Nikiforov, Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl. 432 (9) (2010) 2170–2173.
  * [13] P. Hansen, D. Stevanović, On bags and bugs, Discrete Appl. Math. 156 (2008) 986–997.
  * [14] B. Huo, X. Li, Y. Shi, Complete solution to a conjecture on the maximal energy of unicyclic graphs, European J. Combin. 32 (2011) 662–673.
  * [15] B. Li, B. Ning, Spectral analogues of Erdös’ and Moon-Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra 64(11) (2016) 1152–1169.
  * [16] H. Li, Generalizations of Dirac’s theorem in Hamiltonian graph theory–A survey, Discrete Math. 313 (2013) 2034–2053.
  * [17] J. Li, X. Li, Y. Shi, On the maximal energy tree with two maximum degree vertices, Linear Algebra Appl. 435 (2011) 2272–2284.
  * [18] X. Li, Y. Shi, M. Wei, J. Li, On a conjecture about tricyclic graphs with maximal energy, MATCH Commun. Math. Comput. Chem. 72 (2014) 183–214.
  * [19] J. Li, G. Steiner, Partitioning a graph into vertex-disjoint paths, Studia Sci. Math. Hungar. 42 (2005) 277–294.
  * [20] X. Li, M. Wei, J. Li, Y. Shi, On a conjecture about tricyclic graphs with maximal energy, MATCH Commun. Math. Comput. Chem. 72 (2014) 183–214.
  * [21] Y. Li, Y. Liu, X. Peng, Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree, Linear and Multilinear Algebra 66 (2018) 2011–2023.
  * [22] R. Liu, W.C. Shiu, J. Xue, Sufficient spectral conditions on Hamiltonian and traceable graphs, Linear Algebra Appl. 467 (2015) 254–266.
  * [23] W.J. Liu, M. Liu, L.H. Feng, Spectral conditions for graphs to be $\beta$-deficient involving minimum degree, Linear and Multilinear Algebra 66 (2018), 792–802.
  * [24] W.J. Liu, 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 (2020) 161–179.
  * [25] M. Lu, H. Liu, F. Tian, Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (2012) 1670–1674.
  * [26] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (2010) 2243–2256
  * [27] V. Nikiforov, Spectral radius and Hamiltonicity of graphs with large minimum degree, Czech. Math. Journal 66 (141) (2016) 925–940.
  * [28] B. Ning, J. Ge, Spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra 63 (8) (2015) 1520–1530.
  * [29] G. Steiner, On the $k$-path partition of graphs, Theoretical Computer Science 290 (2003) 2147–2155.
  * [30] D. Stevanović, M. Aouchiche, P. Hansen, On the spectral radius of graphs with a given domination number, Linear Algebra Appl. 428 (2008) 1854–1864.
  * [31] G.D. Yu , Y.Z. Fan, Spectral conditions for a graph to be Hamilton-connected, Applied Mechanics and Materials 336-338 (2013) 2329–2334.
  * [32] M. Zhang, S.C. Li, Extremal Halin graphs with respect to the signless Laplacian spectra, Discrete Appl. Math. 213 (2016) 207–218.
  * [33] X.-D. Zhang, The signless Laplacian spectral radius of graphs with given degree sequence, Discrete Appl. Math. 157 (2009) 2928–2937.
  * [34] 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.
  * [35] B. Zhou, Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl. 432 (2010), 566–570.
  * [36] Q. Zhou, L. Wang, Some sufficient spectral conditions on Hamilton-connected and traceable graphs, Linear Multilinear Algebra 65 (2017) 224–234.
  * [37] Q.N. Zhou, L.G. Wang, Y. Lu, Some sufficient conditions on $k$-connected graphs, Applied Math. Comput. 325 (2018) 332–339