1 Introduction
We deal only with finite and undirected graphs without loops or multiple edges. For graph theoretic notation and terminology not defined here, we refer to [Reference Godsil and Royle4, Reference West13].
Let G be a graph with vertex set
$V(G)$
and edge set
$E(G)$
. The order of G is the number
$n=|V(G)|$
of its vertices and its size is the number
$m=|E(G)|$
of its edges. A graph G is called trivial if
$|V(G)|=1$
. Let
$V_1\subseteq V(G)$
and
$E_1\subseteq E(G)$
. Then,
$G-V_1, G-E_1$
are the graphs formed from G by deleting the vertices in
$V_1$
and their incident edges, or the edges in
$E_1$
, respectively. For convenience, denote
$G-\{v\}$
and
$G-\{uv\}$
by
$G-v$
and
$G-uv$
, respectively. For a given subset
$S\subseteq V(G)$
, the subgraph of G induced by S is denoted by
$G[S]$
. As usual,
$P_n$
and
$K_n$
denote the path and the complete graph on n vertices.
For a vertex
$v\in V(G)$
, let
$N_G(v)$
be the set of all neighbours of v in G. Then,
$d_G(v) = |N_G(v)|$
is the degree of v in G. A vertex v of G is called a pendant vertex if
$d_G(v)=1$
. A quasi-pendant vertex is a vertex being adjacent to some pendant vertex. A graph is r-regular if each vertex has the same degree r. The complement of a graph G is the graph
$\overline {G}$
with the same vertex set as G, in which any two distinct vertices are adjacent if and only if they are nonadjacent in G. For two graphs
$G_1$
and
$G_2$
, we define
$G_1\cup G_2$
to be their disjoint union. The join
$G_1\vee G_2$
is obtained from
$G_1\cup G_2$
by joining every vertex of
$G_1$
with every vertex of
$G_2$
by an edge.
Let
$V(G)=\{v_1,\ldots , v_n\}$
. The adjacency matrix
$A(G)=(a_{ij})$
of G is an
$n\times n$
matrix in which the entry
$a_{ij}$
is 1 or 0 according to whether
$v_i$
and
$v_j$
are adjacent or not. The eigenvalues of the adjacency matrix
$A(G)$
are also called eigenvalues of G. Note that
$A(G)$
is a real symmetric nonnegative matrix. Hence, its eigenvalues are real and can be arranged in nonincreasing order as
$\lambda _1(G)\geqslant \cdots \geqslant \lambda _n(G).$
The spectral radius of G is equal to
$\lambda _1(G)$
, written as
$\rho (G)$
.
Let G be a connected graph with vertex set
$V(G)=\{v_1,\ldots , v_n\}$
and edge set
$E(G)$
. The distance between
$v_i$
and
$v_j$
, denoted by
$d_{ij}$
, is the length of a shortest path from
$v_i$
to
$v_j$
. The Wiener index of G is defined as
$W(G)=\sum _{i<j}d_{ij}$
. The distance matrix of G, denoted by
$D(G)$
, is the
$n\times n$
real symmetric matrix whose
$(i, j)$
-entry is
$d_{ij}$
. We can order the eigenvalues of
$D(G)$
as
$ \lambda _1(D(G))\geqslant \lambda _2(D(G))\geqslant \cdots \geqslant \lambda _n(D(G)). $
By the Perron–Frobenius theorem,
$\lambda _1(D(G))$
is always positive (unless G is trivial) and
$\lambda _1(D(G))\geqslant |\lambda _i(D(G))|$
for
$i=2,3,\ldots ,n$
. We call
$\lambda _1(D(G))$
the distance spectral radius of G, written as
$\mu (G)$
.
A subset S of
$V(G)$
(respectively
$E(G)$
) is called an independent set (respectively a matching) if any two members of S are not adjacent in G. A matching with the maximum size in G is called a maximum matching. The matching number
$\alpha '(G)$
is the size of a maximum matching in G. We call an edge subset S a perfect matching if each vertex of G is incident with an edge in S.
Brouwer and Haemers [Reference Brouwer and Haemers2] proved that if G is an r-regular graph without perfect matchings, then G has at least three proper induced subgraphs
$H_1$
,
$H_2$
and
$H_3$
, which are contained in the family
$$ \begin{align*} \mathscr{H}=\{H: |V(H)|\text{ is odd, }r|V(H)|-r+2\leqslant2|E(H)|\leqslant r|V(H)|-1\}, \end{align*} $$
and that
$\lambda _3(G)\geqslant \min \{\,\rho (H_i): i=1,2,3\}>\min \{{2|E(H)|}/{|V(H)|}: H\in \mathscr {H}\}$
. Quite recently, O [Reference O11] showed that there is a close relationship between the spectral radius and prefect matching not only for regular graphs but also for general graphs. He established sharp upper bounds on the number of edges and the spectral radius of a graph without a perfect matching.
There are several interesting results on the distance spectral radius of G and its matching number. Ilić [Reference Ilić6] characterised n-vertex trees with a given matching number which minimise the distance spectral radius. Liu [Reference Liu7] characterised graphs with minimum distance spectral radius in connected graphs on n vertices with fixed matching number. Zhang [Reference Zhang15] and Lu and Luo [Reference Lu and Luo8] characterised unicyclic graphs with a perfect matching and a given matching number which minimise the distance spectral radius.
A fractional matching of a graph G is a function f giving each edge a number in
$[0,1]$
so that
$\sum _{e\in \Upsilon (v)}f(e)\leqslant 1$
for all
$v\in V(G)$
, where
$\Upsilon (v)$
is the set of edges incident to v. The fractional matching number of G, written as
$\alpha _f'(G)$
, is the maximum of
$\sum _{e\in E(G)}f(e)$
over all fractional matchings f. If
$f(e)\in \{0,1\}$
for every edge e, then f is just a matching, or more precisely, the indicator function of a matching. A fractional perfect matching is a fractional matching f with
$\sum _{e\in E(G)}f(e)={n}/{2}$
. Scheinermann and Ullman [Reference Scheinermann and Ullman12] showed that a graph G has a fractional perfect matching f if and only if
$\sum _{e\in \Upsilon (v)}f(e)=1$
for every
$v\in V(G)$
.
Summing the inequality constraints for all vertices yields
$\sum _{v\in V(G)}\sum _{e\in \Upsilon (v)}f(e)\leqslant n$
, so we always have
$\alpha ^{\prime }_f(G)\leqslant {n}/{2}$
. Since every matching can be viewed as a fractional matching,
$\alpha ^{\prime }_f(G)\geqslant \alpha '(G)$
for all graphs G, but equality need not hold. For example,
$\alpha ^{\prime }_f(G)={n}/{2}$
for an r-regular graph G by setting each edge weight to
${1}/{r}$
, but not every r-regular graph has a perfect matching. In 2016, O [Reference O10] determined the connection between the spectral radius and fractional matching number among connected graphs with given minimum degree.
Motivated by [Reference O10–Reference Scheinermann and Ullman12], it is natural and interesting to give some sufficient conditions to ensure that a graph contains a fractional perfect matching. Here, we focus on sufficient conditions including a structure graph condition, adjacency spectral graph condition and distance spectral graph condition.
Our first main result gives a sufficient condition to ensure a graph G contains a fractional perfect matching according to the size of
$G.$
Theorem 1.1. Let G be an n-vertex connected graph. Then, G contains a fractional perfect matching if
$$ \begin{align*} |E(G)|> \begin{cases} \frac{1}{8}(n-1)(3n-1) & \text{if }\,n=3,5,7,9,11; \\ \frac{3}{8}n(n-2) & \text{if }\,n=4,6,8,10; \\ { 2+\binom{n-2}{2} } & \text{if }n\geqslant12. \end{cases} \end{align*} $$
Our second main result gives a sufficient condition to ensure a graph G contains a fractional perfect matching according to the adjacency spectral radius of G.
Theorem 1.2. Let G be an n-vertex connected graph. Assume the largest roots of
$x^2-\tfrac 12(n-3)x-\tfrac 14(n^2-1)=0$
and
$x^3-(n-4)x^2-(n-1)x+2n-8=0$
are
$\xi _1(n)$
and
$\xi _2(n)$
, respectively. Then, G has a fractional perfect matching if
$$ \begin{align*} \rho(G)> \begin{cases} \sqrt{3} & \text{if }\,n=4; \\ \frac{1}{2}(1+\sqrt{33}) & \text{if }\,n=6; \\ \xi_1(n) & \text{if }\,n=3,5,7,9; \\ \xi_2(n) & \text{if }\,n=8\,\text{ or }\,n\geqslant10. \end{cases} \end{align*} $$
Our last main result gives a sufficient condition to ensure a graph G contains a fractional perfect matching with respect to the distance spectral radius of G.
Theorem 1.3. Let G be an n-vertex connected graph. Assume the largest roots of
$x^2-\tfrac 12(3n-5)x+\tfrac 14(n^2-8n+7)=0,\, x^2-\tfrac 12(3n-4)x+\tfrac 14(n^2-8n+4)=0$
and
$x^3-(n-2)x^2-(7n-17)x-4n+10=0$
are
$\zeta _1(n),\, \zeta _2(n)$
and
$\zeta _3(n)$
, respectively. Then, G contains a fractional perfect matching if
$$ \begin{align*} \mu(G)< \begin{cases} \zeta_1(n) & \text{if }\,n=3,5,7,9,11; \\ \zeta_2(n) & \text{if }\,n=4,6,8; \\ \zeta_3(n) & \text{if }\,n=10\,\text{ or }\,n\geqslant12. \end{cases} \end{align*} $$
The proof techniques in the paper for our main results follow the idea of O [Reference O11]. Our paper is organised as follows. In Section 2, we give some preliminary results. In Section 3, we give the proofs of Theorems 1.1, 1.2 and 1.3. In the last section, we give several extremal graphs to show that all the bounds are best possible.
2 Some preliminaries
In this section, we present some necessary preliminary results, which will be used to prove our main results. The first one follows directly from [Reference Bapat1, Theorem 6.8].
Lemma 2.1 [Reference Bapat1]
Let G be a connected graph and let H be a proper subgraph of G. Then,
$\rho (G)>\rho (H)$
.
Let M be a real symmetric matrix whose rows and columns are indexed by
$V=\{1, \ldots , n\}$
. Assume that M can be written as
$$ \begin{align*} M=\left( \begin{array}{@{}ccc@{}} M_{11} & \cdots & M_{1s} \\ \vdots & \ddots & \vdots \\ M_{s1} & \cdots & M_{ss} \\ \end{array} \right) \end{align*} $$
according to the partition
$\pi : V=V_1\cup \cdots \cup V_s$
, where
$M_{ij}$
denotes the submatrix (block) of M formed by the rows in
$V_i$
and the columns in
$V_j$
. Let
$q_{ij}$
denote the average row sum of
$M_{ij}$
. The matrix
$M_{\pi }=(q_{ij})$
is called the quotient matrix of M. If the row sum of each block
$M_{ij}$
is a constant, then the partition is equitable.
Lemma 2.2 [Reference Brouwer and Haemers3, Reference You, Yang, So and Xi14]
Let M be a real matrix with an equitable partition
$\pi $
and let
$M_{\pi }$
be the corresponding quotient matrix. Then, every eigenvalue of
$M_{\pi }$
is an eigenvalue of M. Furthermore, the largest eigenvalues of M and
$M_{\pi }$
are equal.
Lemma 2.3 [Reference Minc9]
Let G be a connected graph with two nonadjacent vertices
$u,v\in V(G)$
. Then,
$\mu (G+uv)<\mu (G)$
.
The next lemma can be easily derived from the Rayleigh quotient [Reference Horn and Johnson5].
Lemma 2.4. Let G be a connected graph with order n. Then,
$$ \begin{align*}\mu(G)=\max\limits_{\mathbf{x}\neq0}\frac{\mathbf{x}^TD(G)\mathbf{x}}{\mathbf{x}^T\mathbf{x}}\geqslant\frac{\mathbf{1}^TD(G)\mathbf{1}}{\mathbf{1}^T\mathbf{1}}=\frac{2W(G)}{n},\end{align*} $$
where
$\mathbf {1}=(1,1,\ldots ,1)^T$
.
Let
$I(G)$
be the set of isolated vertices of G and let
$i(G)=|I(G)|.$
The next lemma gives a necessary and sufficient condition for a graph to contain a fractional perfect matching.
Lemma 2.5 [Reference Scheinermann and Ullman12]
A graph G contains a fractional perfect matching if and only if
$i(G-S)\leqslant |S|$
for every set
$S\subseteq V(G)$
.
In 2021, O [Reference O11] gave two sufficient conditions to ensure that a graph G contains a perfect matching according to the size and adjacent spectral radius of
$G.$
These results simplify our proof.
Lemma 2.6 [Reference O11]
Let G be an n-vertex connected graph. Then, G contains a perfect matching if
$$ \begin{align*} |E(G)|> \begin{cases} 9 & \text{if }\,n=6; \\ 18 & \text{if }\,n=8; \\ { 2+\binom{n-2}{2} } & \text{if }\,n=4\,\text{ or }\,n\geqslant10\text{ is even.} \end{cases} \end{align*} $$
Lemma 2.7 [Reference O11]
Let G be an n-vertex connected graph. Assume the largest root of
$x^3-(n-4)x^2-(n-1)x+2n-8=0$
is
$\xi _2(n)$
. Then, G has a perfect matching if
$$ \begin{align*} \rho(G)> \begin{cases} \frac{1}{2}(1+\sqrt{33}) & \text{if }n=6; \\ \xi_2(n) & \text{if }\,n=4\text{ or }n\geqslant8\text{ is even.} \end{cases} \end{align*} $$
3 Proofs of our main results
In this section, we give the proofs of Theorems 1.1, 1.2 and 1.3.
Proof of Theorem 1.1
A perfect matching is obviously a fractional perfect matching of a graph. By Lemma 2.6, it is easy to see that our result is true when n is even. Hence, in what follows, we consider the remaining case when n is odd.
Suppose to the contrary that G has no fractional perfect matching. Choose a connected graph G whose size is as large as possible. By Lemma 2.5, there exists a set
$S\subseteq V(G)$
such that
$i(G-S)\geqslant |S|+1$
. According to the choice of G, both the induced graph
$G[S]$
and each connected component of
$G-S$
are complete graphs. Furthermore, G is just the graph
$G[S]\vee (G-S)$
.
Note that there is at most one nontrivial connected component in
$G-S$
. Otherwise, we can add edges among all nontrivial connected components to get a larger nontrivial connected component, which is a contradiction to the choice of G. For convenience, let
$i(G-S)=i$
and
$|S|=s\geqslant 1$
. We proceed by considering two possible cases.
Case 1.
$G-S$
has only one nontrivial connected component, say
$G_1$
.
Let
$|V(G_1)|=n_1\geqslant 2$
. If
$i\geqslant s+2$
, then we construct a new graph
$H_1$
obtained from G by joining each vertex of
$G_1$
with one vertex in
$I(G-S)$
by an edge. Clearly,
$i(H_1-S)=i-1\geqslant s+1$
. By Lemma 2.5,
$H_1$
has no fractional perfect matching. Note that
$|E(H_1)|=|E(G)|+n_1>|E(G)|$
, giving a contradiction with the choice of G.
Since
$i\geqslant s+1$
, we must have
$i=s+1$
. Note that
$n=n_1+2s+1\geqslant 2s+3\geqslant 5$
and
$|E(G)|=s(s+1)+ \binom {n-s-1}{2}$
. Then, by a direct calculation,
$$ \begin{align*} \dbinom{n-2}{2}+2-|E(G)|&=\frac{(s-1)(2n-3s-8)}{2}\\ &\geqslant\frac{(s-1)(4s+6-3s-8)}{2}=\frac{(s-1)(s-2)}{2}\geqslant0. \end{align*} $$
Thus,
$|E(G)|\leqslant \binom {n-2}{2}+2$
for
$n\geqslant 5$
. This is a contradiction for
$n\geqslant 13$
.
For
$n=5,7,9,11$
, by a direct calculation,
$$ \begin{align*} \frac{1}{8}(n-1)(3n-1)-\dbinom{n-2}{2}-2=-\frac{1}{8}n^2+2n-\frac{39}{8} =-\frac{(n-3)(n-13)}{8}>0. \end{align*} $$
Thus,
$|E(G)|\leqslant \binom {n-2}{2} +2<\tfrac 18(n-1)(3n-1)$
, which is a contradiction.
Case 2.
$G-S$
has no nontrivial connected component.
If
$i\geqslant s+3$
, we can create a new graph
$H_2$
by adding an edge in
$I(G-S)$
. Then,
$i(H_2-S)\geqslant s+1$
and
$H_2-S$
has exactly one nontrivial connected component. Together with
$|E(G)|<|E(H_2)|$
and Case 1, we obtain a contradiction. Thus, it suffices to consider
$i=s+1$
in this case (since
$n=2s+2$
is even if
$i=s+2$
).
Assume
$i=s+1$
. Then,
$n=2s+1\geqslant 3$
and
${|E(G)|= \binom {s}{2} + s(s+1) =\tfrac 12(3s^2+s)}$
. Obviously,
$\tfrac 18(n-1)(3n-1)\kern1.2pt{=}\kern1.2pt\tfrac 12(3s^2+s)$
. We get a contradiction when
${n\kern1.2pt{=}\kern1.2pt 3,5,7,9,11}$
. Comparing
$|E(G)|$
with
$\binom {n-2}{2}+2$
gives
$$ \begin{align*} \dbinom{2s-1}{2}+2-|E(G)|=\frac{(s-1)(s-6)}{2}. \end{align*} $$
Thus,
$|E(G)|\leqslant \binom {n-2}{2}+2$
for
$s\geqslant 6$
, which is a contradiction for
$n\geqslant 13$
.
This completes the proof.
Next, based on the idea in the proof of Theorem 1.1, we prove Theorem 1.2 by comparing the spectral radius rather than the number of edges.
Proof of Theorem 1.2
By a similar discussion as the proof of Theorem 1.1, we only consider n odd (based on Lemma 2.7). Suppose to the contrary that G has no fractional perfect matching. Choose a connected graph G of order n such that its adjacency spectral radius is as large as possible.
Note that there does not exist a fractional perfect matching in G. Hence, by Lemma 2.5, there exists a set
$S\subseteq V(G)$
satisfying
$i(G-S)\geqslant |S|+1$
. Together with Lemma 2.1 and the choice of G, the induced graph
$G[S]$
as well as each connected component of
$G-S$
is a complete graph and G is the join of
$G[S]$
and
$G-S$
, that is,
$G=G[S] \vee (G-S)$
.
For convenience, let
$i(G-S)=i$
and
$|S|=s$
. One may see that there exists at most one nontrivial connected component in
$G-S$
. Otherwise, we can add edges among all nontrivial connected components to get a nontrivial connected component of larger size, which gives a contradiction (based on Lemma 2.1). Hence, we proceed by considering the following two possible cases.
Case 1.
$G-S$
has just one nontrivial connected component, say
$G_1$
.
In this case, one has
$|V(G_1)|=n_1\geqslant 2$
. If
$i\geqslant s+2$
, we construct a new graph
$H_1$
obtained from G by joining each vertex of
$G_1$
with one vertex in
$I(G-S)$
by an edge. Then, G is a proper subgraph of
$H_1$
. By Lemma 2.1,
$\rho (G)<\rho (H_1)$
, which is a contradiction.
Now, we assume
$i=s+1$
. Then,
$n=n_1+2s+1\geqslant 2s+3\geqslant 5$
. According to the partition
$V(G)=S\cup I(G-S)\cup V(G_1)$
, the quotient matrix of
$A(G)$
equals
$$ \begin{align*} B_1= \left( \begin{array}{@{}ccc@{}} s-1 & s+1 & n-2s-1\\ s & 0 & 0\\ s & 0 & n-2s-2\\ \end{array} \right). \end{align*} $$
Then, the characteristic polynomial of
$B_1$
is
$$ \begin{align*} \Phi_{B_1}(x)=x^3-(n-s-3)x^2-(s^2+n-2)x+s(s+1)(n-2s-2). \end{align*} $$
Since the partition
$V(G)=S\cup I(G-S)\cup V(G_1)$
is equitable, by Lemma 2.2, the largest root, say
$\theta _1$
, of
$\Phi _{B_1}(x)=0$
equals the spectral radius of G.
Let
$f(x)=x^3-(n-4)x^2-(n-1)x+2n-8$
and let
$\xi _2(n)$
be the largest root of
$f(x)=0$
. Next, we aim to show
$f(\theta _1)<0$
. Substituting
$\theta _1$
for x in
$f(x)-\Phi _{B_1}(x)$
,
$$ \begin{align*} f(\theta_1)-\Phi_{B_1}(\theta_1) &=(1-s)\theta_1^2+(s^2-1)\theta_1-ns^2+2s^3-sn+4s^2+2n+2s-8\\ &=(1-s)\theta_1^2+(s-1)(s+1)\theta_1-(s-1)(sn-2s^2+2n-6s-8)\\ &=(s-1)[-\theta_1(\theta_1-s-1)-(s+2)n+2s^2+6s+8]\\ & \leqslant (s-1)[-\theta_1(\theta_1-s-1)-(s+2)(2s+3)+2s^2+6s+8]. \end{align*} $$
Note that
$K_{s+2}$
is a proper subgraph of G. Hence, by Lemma 2.1,
$\theta _1>s+1$
. Then,
$$ \begin{align*} f(\theta_1)-\Phi_{B_1}(\theta_1) < (s-1)[-(s+2)(2s+3)+2s^2+6s+8] = (s-1)(2-s)\leqslant0. \end{align*} $$
Bear in mind
$\Phi _{B_1}(\theta _1)=0$
. So we obtain
$f(\theta _1)=f(\theta _1)-\Phi _{B_1}(\theta _1)<0$
, which gives
$\rho (G)=\theta _1<\xi _2(n)$
when
$n\geqslant 5$
. This is a contradiction for
$n\geqslant 11$
.
Now consider
$n=5,7,9$
. Let
$\bar {f}(x)=x^2-\tfrac 12(n-3)x-\tfrac 14(n^2-1)$
and let
$\xi _1(n)$
be the largest root of
$\bar {f}(x)=0$
. Since
$\rho (G)=\theta _1<\xi _2(n)$
when
$n\geqslant 5$
, we need to compare
$\xi _2(n)$
with
$\xi _1(n)$
. By a direct calculation,
$\xi _2(5)\thickapprox 2.3429<3=\xi _1(5)$
,
$\xi _2(7)\thickapprox 4.1055<4.6056\thickapprox \xi _1(7)$
,
$\xi _2(9)\thickapprox 6.0492<6.2170\thickapprox \xi _1(9)$
, which is a contradiction.
Case 2.
$G-S$
has no nontrivial connected component.
If
$i\geqslant s+3$
, we can construct a new graph
$H_2$
by adding an edge in
$I(G-S)$
. Then,
$i(H_2-S)\geqslant s+1$
and
$H_2-S$
has one nontrivial connected component. Together with Lemma 2.1 and Case 1, we have
$\rho (G)<\rho (H_2)\leqslant \xi_2 (n)$
, which is a contradiction. Thus, it suffices to consider
$i=s+1$
in this case.
Assume
$i=s+1$
. Consider the partition
$V(G)=S\cup I(G-S)$
. The quotient matrix of
$A(G)$
with respect to the partition
$S\cup I(G-S)$
is equal to
$$ \begin{align*} B_2= \left( \begin{array}{@{}ccc} s-1 & s+1\\ s & 0\\ \end{array} \!\!\right) \end{align*} $$
and the characteristic polynomial of
$B_2$
equals
$ \Phi _{B_2}(x)=x^2-(s-1)x-s(s+1). $
It is easy to see that the partition
$V(G)=S\cup I(G-S)$
is equitable. By Lemma 2.2, the largest root, say
$\theta _2$
, of
$\Phi _{B_2}(x)=0$
equals the spectral radius of G.
Note that
$n=2s+1$
. Then,
$\Phi _{B_2}(x)=\bar {f}(x)$
and
$\theta _2=\xi _1(n)$
. This is a contradiction for
$n=3,5,7,9$
. Next, we consider
$n\geqslant 11$
so that
$s\geqslant 5$
. Substituting
$\theta _2$
for x in
$f(x)-x\Phi _{B_2}(x)$
gives
$$ \begin{align*} f(\theta_2)-\theta_2\Phi_{B_2}(\theta_2) & =(-n+s+3)\theta_2^2+(s^2+s-n+1)\theta_2+2n-8\\ & =(2-s)\theta_2^2+(s^2-s)\theta_2+4s-6\\ & =\theta_2[(2-s)\theta_2+s^2-s]+4s-6. \end{align*} $$
Since
$\theta _2=\tfrac 12(s-1+\sqrt {5s^2+2s+1})>\tfrac 12(s-1+\sqrt {4s^2+4s+1})=\tfrac 32s$
, we have
$$ \begin{align*} f(\theta_2)-\theta_2\Phi_{B_2}(\theta_2) & <\theta_2\bigg[(2-s)\frac{3s}{2}+s^2-s\bigg]+4s-6\\ & =\theta_2\bigg(-\frac{1}{2}s^2+2s\bigg)+4s-6\\ & <-\frac{3}{4}s^3+3s^2+4s-6. \end{align*} $$
Let
$p_1(x)=-\tfrac 34x^3+3x^2+4x-6$
. Then, we have
$p^{\prime }_1(x)=-\tfrac 94x^2+6x+4$
and
$p^{\prime }_1(\tfrac 13(4\pm 4\sqrt {2}))=0$
. Therefore,
$p_1(x)$
is monotonically decreasing for
$x\geqslant 4$
and
$p_1(s)\leqslant p_1(5)=-4.75<0$
when
$s\geqslant 5$
. Thus,
$f(\theta _2)=f(\theta _2)-\theta _2\Phi _{B_2}(\theta _2)<p_1(s)<0$
for
$s\geqslant 5$
and
$\rho (G)=\theta _2<\xi _2(n)$
, which is a contradiction.
Together, Cases 1 and 2 complete the proof.
Finally, we give the proof of Theorem 1.3, again using the idea in the proof of Theorem 1.1.
Proof of Theorem 1.3
Suppose to the contrary that G has no fractional perfect matching. Choose a connected graph G of order n such that its distance spectral radius is as small as possible.
Let
$$ \begin{align*} h(x) &= x^2-\tfrac{1}{2}(3n-5)x+\tfrac{1}{4}(n^2-8n+7), \\ \bar{h}(x) &= x^2-\tfrac{1}{2}(3n-4)x+\tfrac{1}{4}(n^2-8n+4), \\ \tilde{h}(x) &= x^3-(n-2)x^2-(7n-17)x-4n+10. \end{align*} $$
Assume that the largest roots of
$h(x)=0$
,
$\bar {h}(x)=0$
and
$\tilde {h}(x)=0$
are
$\zeta _1(n)$
,
$\zeta _2(n)$
and
$\zeta _3(n)$
(simply
$\zeta _1,\,\zeta _2$
and
$\zeta _3$
), respectively.
By Lemma 2.5, there exists a set
$S\subseteq V(G)$
satisfying
$i(G-S)\geqslant |S|+1$
. Together with Lemma 2.3 and the choice of G, the induced graph
$G[S]$
as well as each connected component of
$G-S$
is a complete graph and G is the join of
$G[S]$
and
$G-S$
, that is,
$G=G[S] \vee (G-S)$
.
For convenience, let
$i(G-S)=i$
and
$|S|=s$
. There exists at most one nontrivial connected component in
$G-S$
. Otherwise, we can obtain a new graph
$G'$
by adding edges among all nontrivial connected components to get a larger nontrivial connected component. By Lemma 2.3, we have
$\mu (G)>\mu (G')$
, which gives a contradiction with our choice. So in what follows, we proceed by considering the two possible cases.
Case 1. There is just one nontrivial connected component, say
$G_1$
, in
$G-S$
.
In this case,
$|V(G_1)|=n_1\geqslant 2$
. If
$i\geqslant s+2$
, we construct a new graph
$H_1$
obtained from G by joining each vertex of
$G_1$
with one vertex in
$I(G-S)$
by an edge. Clearly,
$i(H_1-S)=i-1\geqslant s+1$
. By Lemma 2.5,
$H_1$
also has no fractional perfect matching. In view of Lemma 2.3,
$\mu (G)>\mu (H_1)$
, which is a contradiction to our choice.
Now, we assume
$i=s+1$
. Then,
$n=n_1+2s+1$
. We compare the distance spectral radius of G with that of
$F_n$
, where
$F_n=K_1\vee (K_{n-3}\cup 2K_1)$
and
$\mu (F_n)=\zeta _3(n)$
(see Theorem 4.3 below). According to the partition
$V(G)=S\cup V(G_1)\cup I(G-S)$
, the quotient matrix of
$D(G)$
equals
$$ \begin{align*} M_1= \left( \begin{array}{@{}ccc@{}} s-1 & n-2s-1 & s+1\\ s & n-2s-2 & 2s+2\\ s & 2n-4s-2 & 2s\\ \end{array} \right) \end{align*} $$
and the characteristic polynomial of
$M_1$
is
$$ \begin{align*} \Phi_{M_1}(x)&=x^3-(n+s-3)x^2-(2sn-5s^2+5n-6s-6)x+ns^2\\&\quad -2s^3-sn+2s^2-4n+6s+4. \end{align*} $$
Since the partition
$V(G)=S\cup V(G_1)\cup I(G-S)$
is equitable, by Lemma 2.2, the largest root, say
$\sigma _1$
, of
$\Phi _{M_1}(x)=0$
equals the distance spectral radius of G. Let
$$ \begin{align*} g_1(x)=\Phi_{M_1}(x)-\tilde{h}(x)=(s-1)[-x^2+(-2n+5s+11)x+ns-2s^2+6]. \end{align*} $$
If
$s=1$
, then
$\Phi _{M_1}(x)=\tilde {h}(x)$
and
$\sigma _1=\zeta _3$
. We aim to show
$g_1(\zeta _3)<0$
when
$s\geqslant 2$
.
For
$s\geqslant 2$
, we get
$n=n_1+2s+1\geqslant 2s+3\geqslant 7$
. By Lemma 2.4,
$$ \begin{align*} \zeta_3=\mu(F_n)\geqslant\frac{2W(F_n)}{n}=\frac{n^2+3n-10}{n}=n+3-\frac{10}{n}> n+\frac{3}{2}. \end{align*} $$
Let
$h_1(x)=-x^2+(-2n+5s+11)x+ns-2s^2+6$
be a real function in x, where
$x\in [n+\tfrac 32,+\infty )$
. By a direct calculation,
$h_1'(x)=-2x-2n+5s+11$
and
$h_1"(x)=-2<0$
. Hence,
$h_1'(x)$
is a decreasing function. Consequently,
${h_1'(x)\leqslant h_1'(n+\tfrac 32)=-4n+8+5s.}$
Note that
$n\geqslant 2s+3$
. Thus,
$h_1'(x)\leqslant -3s-4<0$
. That is to say,
$h_1(x)$
is a decreasing function on
$x\in [n+\tfrac 32,+\infty )$
, and so
$$ \begin{align*} h_1(\zeta_3)< h_1(n+\tfrac{3}{2})=-3n^2+(6s+5)n-2s^2+\tfrac{15}{2}s+\tfrac{81}{4}. \end{align*} $$
Let
$h_2(x)=-3x^2+(6s+5)x-2s^2+{15}/{2}s+{81}/{4}$
be a real function in x, where
$x\in [2s+3,+\infty )$
. Then,
$h_2(x)$
is monotonically decreasing for
$x\geqslant 2s+3$
and
$$ \begin{align*}h_2(n)\leqslant h_2(2s+3)=-2s^2-\frac{1}{2}s+\frac{33}{4}=-2\bigg(s-\frac{\sqrt{265}-1}{8}\bigg)\bigg(s+\frac{\sqrt{265}+1}{8}\bigg)<0\end{align*} $$
for
$s\geqslant 2$
. Therefore,
$g_1(\zeta _3)<0$
for
$s\geqslant 2$
. Then,
$\mu (G)=\sigma _1\geqslant \zeta _3$
for
$n\geqslant 5$
, giving a contradiction for
$n=10$
or
$n\geqslant 12$
.
For
$n=5,7,9,11$
, we only need to compare
$\zeta _3$
with
$\zeta _1$
by the proof above. Let
$g_2(x)=\tilde {h}(x)-xh(x)$
. Then,
$$ \begin{align*} g_2(x) =&\frac{1}{2}(n-1)x^2-\bigg(\frac{n^2}{4}+5n-\frac{61}{4}\bigg)x-4n+10. \end{align*} $$
By a direct calculation,
$\zeta _1=\tfrac 14(3n-5+\sqrt {(5n-3)(n+1)})$
. Thus,
$$ \begin{align*} g_2(\zeta_1)&=\frac{n-3}{8}[n\sqrt{(5n-3)(n+1)}+2n^2-11\sqrt{(5n-3)(n+1)}-32n+26]\\ &=\frac{n-3}{8}[(n-11)\sqrt{(5n-3)(n+1)}+(2n^2-32n+26)]\\ &=\frac{n-3}{8}[(n-11)\sqrt{(5n-3)(n+1)}+2(n-8-\sqrt{51})(n-8+\sqrt{51})]. \end{align*} $$
Since
$5\leqslant n\leqslant 11$
, we get
$g_2(\zeta _1)<0$
. Then,
$\zeta _3>\zeta _1$
, and so
$\mu (G)>\zeta _1$
, which is a contradiction.
Similarly, for
$n=6,8$
, it suffices to compare
$\zeta _3$
with
$\zeta _2$
. By a direct calculation, we have
$\zeta _2(6)\thickapprox 7.2749<7.5546\thickapprox \zeta _3(6)$
and
$\zeta _2(8)\thickapprox 9.8990<10.0839\thickapprox \zeta _3(8)$
. Then,
$\mu (G)>\zeta _2$
, which is a contradiction.
Case 2. There does not exist any nontrivial connected component in
$G-S$
.
If
$i\geqslant s+3$
, we can construct a new graph
$H_2$
by adding an edge in
$I(G-S)$
. Then,
$i(H_2-S)\geqslant s+1$
and
$H_2-S$
has one nontrivial connected component. Together with Lemma 2.3 and Case 1, we obtain a contradiction. Thus, it suffices to consider
$i=s+1$
and
$i=s+2$
.
For
$i=s+1$
, the quotient matrix of
$D(G)$
for the partition
$V(G)=S\cup I(G-S)$
is
$$ \begin{align*} M_2= \bigg( \begin{array}{@{}ccc} s-1 & s+1\\ s & 2s\\ \end{array}\!\! \bigg) \end{align*} $$
and the characteristic polynomial of
$M_2$
equals
$ \Phi _{M_2}(x)=x^2-(3s-1)x+s^2-3s. $
Since the partition
$V(G)=S\cup I(G-S)$
is equitable, by Lemma 2.2, the largest root, say
$\sigma _2$
, of
$\Phi _{M_2}(x)=0$
equals the distance spectral radius of G.
Note that
$n=2s+1$
. Then,
$\Phi _{M_2}(x)=h(x)$
and
$\sigma _2=\zeta _1$
. We can get a contradiction when
$n=3,5,7,9,11$
. For
$s=6$
(
$n=13$
), one has
${\mu (G)\kern1.3pt{=}\kern1.3pt\sigma _2\kern1.3pt{\thickapprox}\kern1.3pt 15.8655\kern1.3pt{>}\kern1.3pt15.8393\kern1.3pt{\thickapprox}\kern1.3pt \zeta _3}$
. Next, we consider
$s\geqslant 7$
. Note that
$n=2s+1\geqslant 15$
. By Lemma 2.4, it follows that
$\zeta _3\geqslant n+3-{10}/{n}>n+2=2s+3$
. Let
$\bar {g}(x)=x\Phi _{M_2}(x)-\tilde {h}(x)$
. Then,
$$ \begin{align*} \bar{g}(x) =&-sx^2+(s^2+11s-10)x+8s-6. \end{align*} $$
It is easy to check that
$\bar {g}(x)$
is a monotonically decreasing function for
$x\geqslant 2s+3$
, and so
$\bar {g}(\zeta _3)\leqslant \bar {g}(2s+3)=-2s^3+13s^2+12s-36$
.
Let
$h_3(x)=-2x^3+13x^2+12x-36$
, where
$x\in [7,+\infty )$
. Then,
$h^{\prime }_3(x)=-6x^2+26x+12=-6(x-\tfrac 16(13+\sqrt {241}))(x-\tfrac 16(13-\sqrt {241}))<0$
and
$\bar {g}(\zeta _3)\leqslant h_3(s)\leqslant h_3(7) =-1<0$
when
$s\geqslant 7$
. Thus,
$\mu (G)>\zeta _3(n)$
for
$n\geqslant 13$
, which is a contradiction.
For
$i=s+2$
, the quotient matrix of
$D(G)$
for the partition
$V(G)=S\cup I(G-S)$
is
$$ \begin{align*} M_3= \bigg( \begin{array}{@{}ccc} s-1 & s+2\\ s & 2s+2\\ \end{array} \!\!\bigg) \end{align*} $$
and the characteristic polynomial of the matrix
$M_3$
is
$ \Phi _{M_3}(x)=x^2-(3s+1)x+s^2-2s-2. $
Since the partition
$V(G)=S\cup I(G-S)$
is equitable, by Lemma 2.2, the largest root, say
$\sigma _3$
, of
$\Phi _{M_3}(x)$
equals the distance spectral radius of G.
Recall that
$n=2s+2$
. It is easy to see that
$\Phi _{M_3}(x)=\bar {h}(x)$
and
$\sigma _3=\zeta _2$
. Thus, we get a contradiction when
$n=4,6,8$
. If
$s=4$
, then
$n=10$
and
$\mu (G)=\sigma _3\thickapprox 12.5208>12.4504\thickapprox \zeta _3(10)$
. Next, we consider
$s\geqslant 5$
. Note that
$n\geqslant 12$
and
$\zeta _3\geqslant n+3-{10}/{n}>n+2=2s+4$
by Lemma 2.4. Let
$$ \begin{align*} \tilde{g}(x)=x\Phi_{M_3}(x)-\tilde{h}(x) =-(s+1)x^2+(s^2+12s-5)x+8s-2. \end{align*} $$
By a direct calculation,
$\tilde {g}(x)$
is a monotonically decreasing function for
$x\geqslant 2s+4$
and
$\tilde {g}(\zeta _3)<\tilde {g}(2s+4)=-2s^3+8s^2+14s-38$
.
Let
$h_4(x)=-2x^3+8x^2+14x-38$
be a real function in x, where
$x\in [5,+\infty )$
. Then,
$h^{\prime }_4(x)=-6s^2+16s+14=-6(x-\tfrac 13(4+\sqrt {37}))(x-\tfrac 13(4-\sqrt {37}))<0$
and
$\tilde {g}(\zeta _3)<h_4(s)\leqslant h_4(5)=-18<0$
. Thus,
$\mu (G)>\zeta _3(n)$
for
$n\geqslant 12$
and
$n=10$
, which is a contradiction.
Together, Case 1 and Case 2 complete the proof.
4 Extremal graphs
In this section, we construct several graphs to show that the bounds established in Theorems 1.1, 1.2 and 1.3 are sharp.
Theorem 4.1. Let n be a positive integer.
-
(i) For
$n=3,5,7,9,11$
, we have
$|E(\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}})|=\tfrac 18(n-1)(3n-1)$
and
$\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}}$
has no fractional perfect matching. -
(ii) For
$n=4,6,8,10$
, we have
$|E(\overline {K_{{(n+2)}/{2}}}\vee K_{{(n-2)}/{2}})|=\tfrac 38n(n-2)$
and
$\overline {K_{{(n+2)}/{2}}}\vee K_{({n-2)}/{2}}$
has no fractional perfect matching. -
(iii) For
$n\geqslant 12$
, we have
$|E(K_1\vee (K_{n-3}\cup 2K_1))|=\binom {n-2}{2}+2$
and
$K_1\vee (K_{n-3}\cup 2K_1)$
has no fractional perfect matching.
Proof. It is straightforward to check the sizes of graphs
$\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}}$
,
$\overline {K_{{(n+2)}/{2}}}\vee K_{{(n-2)}/{2}}$
and
$K_1\vee (K_{n-3}\cup 2K_1)$
. However, put
$S=V(K_{{(n-1)}/{2}})$
,
$V(K_{{(n-2)}/{2}})$
and
$V(K_1)$
. By Lemma 2.5,
$\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}}$
,
$\overline {K_{{(n+2)}/{2}}}\vee K_{{(n-2)}/{2}}$
and
$K_1\vee (K_{n-3}\cup 2K_1)$
) have no fractional perfect matching.
Theorem 4.2. Let n be a positive integer.
-
(i) For
$n=4$
, we have
$\rho (\overline {K_3}\vee K_1)=\sqrt {3}$
and
$\overline {K_3}\vee K_1$
has no fractional perfect matching. -
(ii) For
$n=6$
, we have
$\rho (\overline {K_4}\vee K_2)=\tfrac 12(1+\sqrt {33})$
and
$\overline {K_4}\vee K_2$
has no fractional perfect matching. -
(iii) For
$n=3,5,7,9$
, we have
$\rho (\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}})=\xi _1(n)$
and
$\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}}$
has no fractional perfect matching, where
$\xi _1(n)$
is the largest root of the polynomial
$x^2-\tfrac 12(n-3)x-\tfrac 14(n^2-1)=0$
. -
(iv) For
$n=8$
or
$n\geqslant 10$
, we have
$\rho (K_1\vee (K_{n-3}\cup 2K_1))=\xi _2(n)$
, and the graph
$K_1\vee (K_{n-3}\cup 2K_1)$
has no fractional perfect matching, where
$\xi _2(n)$
is the largest root of the polynomial
$x^3-(n-4)x^2-(n-1)x+2n-8=0$
.
Proof. Here we only prove item (iv). A similar discussion shows items (i), (ii) and (iii).
According to the partition
$V(2K_1)\cup V(K_1)\cup V(K_{n-3})$
, the quotient matrix of
$A(K_1\vee (K_{n-3}\cup 2K_1))$
can be written as
$$ \begin{align*} B(K_1\vee(K_{n-3}\cup2K_1))= \left( \begin{array}{@{}cccc} 0 & 1 & 0 \\ 2 & 0 & n-3 \\ 0 & 1 & n-4 \\ \end{array} \right), \end{align*} $$
whose characteristic polynomial is
$x^3-(n-4)x^2-(n-1)x+2n-8$
. Since the vertex partition is equitable, the largest root
$\xi _2(n)$
of
$x^3-(n-4)x^2-(n-1)x+2n-8=0$
is equal to the spectral radius of
$K_1\vee (K_{n-3}\cup 2K_1)$
. Let
$S=V(K_1)$
. By Lemma 2.5,
$K_1\vee (K_{n-3}\cup 2K_1)$
has no fractional perfect matching.
This completes the proof of item (iv).
Theorem 4.3. Let n be a positive integer.
-
(i) For
$n=3,5,7,9,11$
, we have
$\mu (\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}})=\zeta _1(n)$
and
$\overline {K_{{(n+1)}/{2}}}\vee K_{{(n-1)}/{2}}$
has no fractional perfect matching, where
$\zeta _1(n)$
is the largest root of the polynomial
$x^2-\tfrac 12(3n-5)x+\tfrac 14(n^2-8n+7)=0$
. -
(ii) For
$n=4,6,8$
, we have
$\mu (\overline {K_{{(n+2)}/{2}}}\vee K_{{(n-2)}/{2}})=\zeta _2(n)$
and
$\overline {K_{{(n+2)}/{2}}}\vee K_{{(n-2)}/{2}}$
has no fractional perfect matching, where
$\zeta _2(n)$
is the largest root of the polynomial
$x^2-\tfrac 12(3n-4)x+\tfrac 14(n^2-8n+4)=0$
. -
(iii) For
$n=10$
and
$n\geqslant 12$
, we have
$\mu (K_1\vee (K_{n-3}\cup 2K_1))=\zeta _3(n)$
and the graph
$K_1\vee (K_{n-3}\cup 2K_1)$
has no fractional perfect matching, where
$\zeta _3(n)$
is the largest root of
$x^3-(n-2)x^2-(7n-17)x-4n+10=0$
.
Proof. Here we only prove item (iii). A similar discussion shows items (i) and (ii).
According to the partition
$V(2K_1)\cup V(K_1)\cup V(K_{n-3})$
, the quotient matrix of
$D(K_1\vee (K_{n-3}\cup 2K_1))$
can be written as
$$ \begin{align*} B(K_1\vee(K_{n-3}\cup2K_1))= \left( \begin{array}{@{}cccc@{}} 2 & 1 & 2n-6 \\ 2 & 0 & n-3 \\ 4 & 1 & n-4 \\ \end{array} \!\!\right), \end{align*} $$
whose characteristic polynomial is
$x^3-(n-2)x^2-(7n-17)x+-4n+10$
. Since the vertex partition is equitable, the largest root
$\zeta _3(n)$
of
${x^3\kern1.2pt{-}\kern1.2pt(n\kern1.2pt{-}\kern1.2pt2)x^2\kern1.2pt{-}\kern1.2pt(7n\kern1.2pt{-}\kern1.2pt17)x\kern1.2pt{-}\kern1.2pt4n\kern1.2pt{+}\kern1.2pt10}$
is equal to the spectral radius of
$K_1\vee (K_{n-3}\cup 2K_1)$
. Let
$S=V(K_1)$
. By Lemma 2.5,
$K_1\vee (K_{n-3}\cup 2K_1)$
has no fractional perfect matching.
This completes the proof of item (iii).
