Maximum degree and spectral radius of graphs in terms of size

Abstract

Denote by $\rho (G)$ and $\kappa (G)$ the spectral radius and the signless Laplacian spectral radius of a graph G, respectively. Let $k\ge 0$ be a fixed integer and G be a graph of size m which is large enough. We show that if $\rho (G)\ge \sqrt{m-k}$, then $C_4\subseteq G$ or $K_{1,m-k}\subseteq G$. Moreover, we prove that if $\kappa (G)\ge m-k+1$, then $K_{1,m-k}\subseteq G$. Both these results extend some known results.

1 Introduction

Graphs considered in the paper are simple and undirected. For a graph G, let $\rho (G)$ be the spectral radius of its adjacency matrix A(G), and $\kappa (G)$ be the spectral radius of its signless Laplacian matrix $\kappa (G)$. From the Perron–Frobenius theorem, for a connected graph G, the adjacency (resp., signless Laplacian) spectral radius of G is the maximum modulus of its adjacency (resp., signless Laplacian) eigenvalues. In general, we call $\rho (G)$ the spectral radius of G, and $\kappa (G)$ the signless Laplacian spectral radius of G.

It is well known that the structural properties and parameters of graphs have a close relationship with the eigenvalues of graphs. During the recent 30 years, the (signless Laplacian) spectral radius among graphs with described structures properties has attracted considerable attention.

For a graph G, we call H a subgraph of G if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$; in addition, H is an induced subgraph of G if an edge $uv\in E(H)$ if and only if $uv\in E(G)$. A graph G is defined to be H-free if G does not contain H as a subgraph (not necessarily induced). As a spectral version of Turán type problem, the spectral Turán type problem received much attention from many scholars. In 2010, Nikiforov [12] posed the associated problem that what is the maximal spectral radius $\rho (G)$ among H-free graphs G of order n? This problem is also known as the Brualdi–Solheid–Turán type problem and has been investigated in much literature for some special graphs H, for which one can refer to clique [10], book [22], friendship [2], and the references therein.

Replacing the order n by the size m, many scholars recently paid their attention to a perspective of spectral Turán type problem in terms of the size: what is the maximal spectral radius $\rho (G)$ among H-free graphs G of size m? To the best of our knowledge, the history of studying this problem may be dated back at least to Nosal’s theorem [15] in 1970. Up to now, there are few graphs H such that the maximal spectral radius $\rho (G)$ among H-free graphs of size m has been studied and bounded by a fixed value. Some relevant conclusions have been obtained in the past two decades. Nikiforov in [9] extended Nosal’s theorem from triangle to clique and in [14] answered a conjecture by Zhai, Lin, and Shu [23] about books. For more detailed results, we refer to [7, 23].

Here, we pay our main attention to the spectral Turán type problems on quadrilaterals and stars in terms of the size. Let $K_{1,n-1}$ and $C_n$ be a star and a cycle on n vertices, respectively. Denote by $K_{1,n-1}+e$ the graph by inserting an edge to the independent set of $K_{1,n-1}$, and denote by $K_{1,n-1}^e$ the graph by attaching a pendent vertex to a pendent vertex of $K_{1,n-1}$.

In [11], Nikiforov provided an upper bound of the maximum spectral radius among all $C_4$-free graphs of size m.

Theorem 1

[11] Let G be a graph of size $m\ge 9$. If $\rho (G)>\sqrt{m}$, then $C_4\subseteq G$.

Zhai and Shu [24] improved the result in Theorem 1 for a non-bipartite connected graph by showing the following theorem.

Theorem 2

[24] Let G be a non-bipartite and connected graph of size $m\ge 26$. If $\rho (G)\ge \rho (K_{1,m-1}+e)$, then $C_4\subseteq G$ unless G is $K_{1,m-1}+e$.

Recently, Wang [19] provided a generalization of Theorems 1 and 2.

Theorem 3

[19] Let G be a graph of size $m\ge 27$. If $\rho (G)\ge \sqrt{m-1}$, then $C_4\subseteq G$ unless G is one of these graphs (with possibly isolated vertices): $K_{1,m}$, $K_{1,m-1}+e$, $K_{1,m-1}^e$, or $K_{1,m-1}\cup P_2$.

It is easy to check that $\rho (H)<\rho (K_{1,m})$ if $H\in \{K_{1,m-1}+e, K_{1,m-1}^e, K_{1,m-1}\cup P_2\}$ and $m\ge 27$. This, together with Theorems 1 and 3, indicates that if $\rho (G)\ge \sqrt{m}$ for a graph G of size $m\ge 27$, then $C_4\subseteq G$ unless G is $K_{1,m}$. Indeed, from Theorems 1 and 3, if $m\ge 27$ and $\rho (G)\ge \sqrt{m-k}$ for $k=0$ or 1, then $C_4\subseteq G$ unless $K_{1,m-k}\subseteq G$. Motivated by this, we hope to give a general result in terms of the value of k.

Theorem 4

Let $k\ge 0$ be an integer and G be a graph of size $m\ge \max \{(k^2+2k+2)^2+k+1,(2k+3)^2+k+1\}$. If $\rho (G)\ge \sqrt{m-k}$, then $K_{1,m-k}\subseteq G$ or $C_4\subseteq G$.

Next, we turn our attention to the study of a relationship between the maximum degree and the signless Laplacian spectral radius of a graph. The signless Laplacian matrix Q(G) is a linear combination of adjacency matrix and diagonal matrix of a graph G, so it may significantly reveal the structural properties of the graph G. As expressed in [18], among matrices (generalized adjacency matrices) associated with a graph, the signless Laplacian matrix seems to be the most convenient for using in studying graph properties. For the related researches on the signless Laplacian matrix, the readers may refer to [8, 16, 20], and a series of surveys by Cvetković and Simić [3,4,5].

A signless spectral Turán type version of extremal graph theory has been extensively studied by researchers. In terms of the order of a graph, much literature investigated the maximal signless Laplacian spectral radius $\kappa (G)$ among H-free graphs for various graphs H, including triangles [27], cycles [13, 21], and linear forests [1]. However, there are few investigations on signless spectral Turán type problems in terms of the size.

The topic we focus on is inspired by a theorem by Zhai, Xue, and Lou [26], which can be viewed as a signless Laplacian spectral Turán type problem for stars in terms of the size.

Theorem 5

[26] Let G be a graph of size $m\ge 4$. If G is a graph without isolated vertices, then $\kappa (G)\le m + 1$ with equality if and only if $G= K_{1,m}$.

Theorem 5 infers that if $\kappa (G)\ge m+1$ for a graph of size m, then $K_{1,m}\subseteq G$ (in fact, $G=K_{1,m}$ when G has no isolated vertex). We show the following result, which extends Theorem 5.

Theorem 6

Let $k\ge 0$ be an integer and G be a graph of size $m\ge \max \{\frac{1}{2}k^2+6k+3, 7k+25\}$. If $\kappa (G)\ge m-k+1$, then $K_{1,m-k}\subseteq G$.

Remark 1.1

Let $G_1$ (resp. $G_2$) be the graph from $K_{1,m-k-1}$ (resp. $K_{1,m-k}$) by embedding $k+1$ (resp. k) independent edges. We may check $\rho (G_1)<\sqrt{m-k}$, $\kappa (G_1)<m-k+1$, $\rho (G_2)>\sqrt{m-k}$ and $\kappa (G_2)>m-k+1$. Moreover, we know $G_1$ does not contain neither $K_{1,m-k}$ nor $C_4$ as a subgraph, and $G_2$ contains $K_{1,m-k}$ as a subgraph. Thus, $G_1$ and $G_2$ illustrate Theorems 4 and 6.

Remark 1.2

Let $m=\left( {\begin{array}{c}s\\ 2\end{array}}\right) +t$ ($0\le t\le s-1$) and G be the graph from $K_s$ by attaching k pendant edges at a vertex of $K_s$. We have $\rho (G)>\sqrt{m-k}$ if m satisfies the condition in Theorem 4. However, G contains $C_4$ as a subgraph but not an induced subgraph. So we always consider an F-free graph as a graph does not contain F as a subgraph.

The rest of this paper is organized as follows. Notations are introduced in Sect. 2. Proofs of Theorems 4 and 6 are presented in Sects. 2 and 3, respectively. In Sect. 4, we propose a conjecture on the relation between the maximum degree and spectral radius of adjacency matrix in terms of order.

2 Proof of theorem 4

We shall introduce terminology and notation. For a graph G, let u be a vertex of G, and S, T be two subsets of V(G). Then, let $N_S(u)$ denote the set of neighbors of u in S, and $d_S(u)$ be the cardinality of $N_S(u)$, i.e., $d_S(u)=|N_S(u)|$. Specially, if $S=V(G)$ then we omit the subscript S. The minimum degree of G is defined to be $\delta (G)=\min \{d(u):u\in V(G)\}$. Let G[S] be the subgraph of G induced by S, and denote by E(S) the set of edges in G[S] and e(S) the cardinality of E(S). Suppose that $S\cap T=\varnothing$. Then, we denote by e(S, T) the number of edges with one vertex in S and the other vertex in T.

Now we prove Theorem 4 by way of contradiction. Assume that there are graphs H of size $m\ge \max \{(k^2+2k+2)^2+k+1,(2k+3)^2+k+1\}$ with $\rho (H)\ge \sqrt{m-k}$, such that $K_{1,m-k}\not \subseteq H$ and $C_4\not \subseteq H$. Let G be a graph with the maximum spectral radius among graphs satisfying the above conditions. Since adding/deleting isolated vertices to/from G not changes the value of $\rho (G)$, we can let G contain no isolated vertices. For simplification, we write $\rho$ by $\rho (G)$.

Let ${{{\varvec{x}}}}$ be a nonnegative eigenvector of A(G) corresponding to $\rho$ with coordinate $x_i$ corresponding to the vertex $v_i$ of G. Let $u^*$ be a vertex of G with $x_{u^*}=\max \{x_i:v_i\in V(G)\}$, then we have a partition $\{u^*\}\cup A\cup B$ of V(G) where $A=N(u^*)$ and $B=V(G)\backslash N[u^*]$. Thus,

$$\begin{aligned} \rho ^2x_{u^*}&=\sum _{u\in N(u^*)}\rho x_u =\sum _{u\in N(u^*)}\sum _{v\in N(u)}x_v\nonumber \\&=|A|x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v)+\sum _{u\in B}d_A(u)x_u. \end{aligned}$$

(1)

Next, we establish two necessary claims.

Claim 1

For a vertex u in B, $d_A(u)\le 1$.

Proof

This claim follows from the fact that $C_4\not \subseteq G$. $\square$

Following the partition of V(G), we give a refinement of B. Let $B=B_1\cup B_2$ be a partition of B, such that $B_1=\{u\in B: d_B(u)=0\}$ and $B_2=B\backslash B_1$. For a vertex $u\in B_1$, we have $d_A(u)=1$ from Claim 1, and so $d(u)=1$.

Claim 2

For a vertex u in $B_1$, $x_u\le \frac{1}{\rho }x_{u^*}$.

Proof

Let $u\in B_1$, then we have $\rho x_u=\sum _{v\in N(u)}x_v\le x_{u^*}$. The claim follows. $\square$

Thus, from Claim 2, by (1) we have

$$\begin{aligned} \rho ^2x_{u^*}\le |A|x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v)+\sum _{u\in B_1}\frac{1}{\rho }x_{u^*}+\sum _{u\in B_2}d_A(u)x_u. \end{aligned}$$

(2)

Note that

$$\begin{aligned} e(A,B_2)\le 2e(B_2)=2e(B). \end{aligned}$$

(3)

Note that V(G) has the partition $\{u^*\}\cup A\cup B_1\cup B_2$. Clearly $P_3\not \subseteq G[A]$ since $C_4\not \subseteq G$. Then, from Claim 2, by (3) we obtain

$$\begin{aligned} \rho \sum _{uv\in E(A)}(x_u+x_v)&= 2e(A)x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v) +\sum _{u\in B_1}d_A(u)x_u+\sum _{u\in B_2}d_A(u)x_u\\&\le 2e(A)x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v) +\frac{e(A,B_1)}{\rho }x_{u^*}+e(A,B_2)x_{u^*}\\&\le 2e(A)x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v) +\frac{e(A,B_1)}{\rho }x_{u^*}+2e(B)x_{u^*}. \end{aligned}$$

It follows that

$$\begin{aligned} \sum _{uv\in E(A)}(x_u+x_v)\le \left( \frac{2e(A)+2e(B)}{\rho -1} {+}\frac{e(A,B_1)}{\rho (\rho -1)}\right) x_{u^*}. \end{aligned}$$

This, together with (2), indicates

$$\begin{aligned} \rho ^2 x_{u^*}&{\le } |A|x_{u^*}{+}\left( \frac{2e(A){+}2e(B)}{\rho -1}{+}\frac{e(A,B_1)}{\rho (\rho -1)}\right) x_{u^*}{+} \frac{e(A,B_1)}{\rho }x_{u^*} {+}\sum _{u\in B_2}d_A(u)x_u\\&{\le }|A|x_{u^*}{+}\left( \frac{2e(A)+2e(B)}{\rho -1} {+}\frac{e(A,B_1)}{\rho (\rho -1)}\right) x_{u^*} {+} \frac{e(A,B_1)}{\rho }x_{u^*} {+}e(A,B_2)x_{u^*}\\&=\left( |A|+\frac{2e(A)+2e(B)}{\rho -1}+\frac{e(A,B_1)}{\rho -1} +e(A,B_2)\right) x_{u^*}. \end{aligned}$$

That is, $\rho ^2\le |A|+\frac{2e(A)+2e(B)}{\rho -1}+\frac{e(A,B_1)}{\rho -1}+e(A,B_2)$.

On the other hand, we know that $\rho ^2\ge m-k$. Note that $m=|A|+e(A)+e(B)+e(A,B)=|A|+e(A)+e(B)+e(A,B_1)+e(A,B_2)$. We have

$$\begin{aligned} \rho ^2\ge |A|+e(A)+e(B)+e(A,B_1)+e(A,B_2)-k. \end{aligned}$$

(4)

Hence,

$$\begin{aligned}{} & {} |A|+e(A)+e(B)+e(A,B_1)+e(A,B_2)-k\\{} & {} \quad \le |A|+\frac{2e(A)+2e(B)}{\rho -1}+\frac{e(A,B_1)}{\rho -1}+e(A,B_2), \end{aligned}$$

which implies

$$\begin{aligned} (\rho -3)e(A)+(\rho -3)e(B)+(\rho -2)e(A,B_1)\le k(\rho -1). \end{aligned}$$

Since $m\ge (2k+3)^2+k+1$, we have $\rho \ge \sqrt{m-k}>2k+3$. Thus, $e(B)\le \frac{\rho -1}{\rho -3}k<k+1$, and so $e(B)\le k$.

Therefore, for a vertex $u\in B_2$, we have $d(u)\le k+1$, and

$$\begin{aligned} \rho x_u=\sum _{v\in N(u)}x_v\le d(u)x_{u^*}\le (k+1)x_{u^*}, \end{aligned}$$

which follows that $x_u\le \frac{k+1}{\rho }x_{u^*}$. Furthermore, we obtain

$$\begin{aligned} \rho \sum _{uv\in E(A)}(x_u+x_v)&\le 2e(A)x_{u^*} +\sum _{uv\in E(A)}(x_u+x_v)+\sum _{u\in B_1}d_A(u)x_u +\sum _{u\in B_2}d_A(u)x_u\\&\le 2e(A)x_{u^*}+\sum _{uv\in E(A)}(x_u+x_v) +\frac{e(A,B_1)}{\rho }x_{u^*}+\frac{(k+1) e(A,B_2)}{\rho }x_{u^*}. \end{aligned}$$

That is,

$$\begin{aligned} \sum _{uv\in E(A)}(x_u+x_v)\le \frac{1}{\rho -1}\left( 2e(A) +\frac{e(A,B_1)}{\rho }+\frac{(k+1)e(A,B_2)}{\rho }\right) x_{u^*}. \end{aligned}$$

By (2), we have

$$\begin{aligned} \rho ^2 x_{u^*}&\le |A|x_{u^*}+\frac{1}{\rho -1}\left( 2e(A)+\frac{e(A,B_1)}{\rho } +\frac{(k+1)e(A,B_2)}{\rho }\right) x_{u^*}+ \frac{e(A,B_1)}{\rho }x_{u^*}\\&\quad +\sum _{u\in B_2}d_A(u)x_u\\&\le |A|x_{u^*}+\frac{1}{\rho -1}\left( 2e(A)+\frac{e(A,B_1)}{\rho } +\frac{(k+1)e(A,B_2)}{\rho }\right) x_{u^*}+ \frac{e(A,B_1)}{\rho }x_{u^*}\\&\quad +\frac{(k+1)e(A,B_2)}{\rho }x_{u^*}\\&=\left( |A|+\frac{2e(A)}{\rho -1}+\frac{e(A,B_1)}{\rho -1} +\frac{(k+1)e(A,B_2)}{\rho -1}\right) x_{u^*}. \end{aligned}$$

Combining this inequality with (4), we obtain

$$\begin{aligned}{} & {} |A|+e(A)+e(B)+e(A,B_1)+e(A,B_2)-k\\{} & {} \quad \le |A|+\frac{2e(A)}{\rho -1}+\frac{e(A,B_1)}{\rho -1}+\frac{(k+1)e(A,B_2)}{\rho -1}, \end{aligned}$$

which implies

$$\begin{aligned} (\rho -3)e(A)+(\rho -1)e(B)+(\rho -2)e(A,B_1) +(\rho -k-2)e(A,B_2)\le k(\rho -1). \end{aligned}$$

(5)

By $K_{1,m-k}\not \subseteq G$, we have $e(A)+e(B)+e(A,B_1)+e(A,B_2)=m-|A|\ge k+1$. If $k=0$, then $(\rho -3)e(A)+(\rho -1)e(B)+(\rho -2)e(A,B_1)+(\rho -2)e(A,B_2)\le 0$ by (5). So $\rho \le 3$. Hence, $3\ge \rho \ge \sqrt{m-k}\ge \sqrt{(2k+3)^2+k+1-k}=\sqrt{10}$, a contradiction.

If $k\ge 1$, then by (5) we have

$$\begin{aligned} e(A)+e(B)+e(A,B_1)+e(A,B_2)\le \frac{\rho -1}{\rho -k-2}k<k+1 \end{aligned}$$

since $\rho \ge \sqrt{m-k}\ge \sqrt{(k^2+2k+2)^2+k+1-k}>k^2+2k+2$. This is a contradiction.

This completes the proof of Theorem 4.

3 Proof of theorem 6

We resume the notation from the previous section. For a graph G, if ${{{\varvec{x}}}}$ is a unit eigenvector of Q(G) corresponding to $\kappa (G)$ with coordinate $x_i$ corresponding to the vertex $v_i$ of G, by the well-known Courant–Fischer theorem (see eg., [6, Theorem 4.2.6]), then we have

$$\begin{aligned} \kappa (G)=\max _{\Vert {{\textbf {y}}}\Vert _2=1}{{\textbf {y}}}^T Q(G){{\textbf {y}}}=\sum _{v_iv_j\in E(G)}(x_i+x_j)^2. \end{aligned}$$

(6)

Note that the formulate $Q(G){{{\varvec{x}}}}=\kappa (G){{{\varvec{x}}}}$ implies that $\big (\kappa (G)I-D(G)\big ){{{\varvec{x}}}}=A(G){{{\varvec{x}}}}$. Then for a vertex $u\in V(G)$, we have

$$\begin{aligned} \big (\kappa (G)-d(u)\big )x_u=\sum _{v\in N(u)}x_v. \end{aligned}$$

(7)

Now we prove Theorem 6 by way of contradiction. Suppose that G is the extremal graph with the maximum signless Laplacian spectral radius among graphs H of size $m\ge \max \{\frac{1}{2}k^2+6k+3, 7k+25\}$ and $K_{1,m-k}\not \subseteq H$. Then, $\kappa (G)\ge m-k+1$. Let ${{{\varvec{x}}}}$ be a nonnegative unit eigenvector of Q(G) corresponding to $\kappa (G)$, and $u^*$ be a vertex of G with $x_{u^*}=\max \{x_i:v_i\in V(G)\}$. For simplification, write $\kappa$ by $\kappa (G)$.

Denote by

$$\begin{aligned} W=\left\{ u\in V(G): x_u\ge \frac{1}{2}x_{u^*}\right\} . \end{aligned}$$

Note that $u^*\in W$, and $|W|\ge 1$. We prove the following claim.

Claim 3

$|W|=1$.

Proof

For a vertex $u\in W$, we know $x_u\ge \frac{1}{2}x_{u^*}$. Then, by (7),

$$\begin{aligned} \big (\kappa -d(u)\big )\frac{1}{2}x_{u^*}\le \big (\kappa -d(u)\big )x_u=\sum _{v\in N(u)}x_v\le d(u)x_{u^*}, \end{aligned}$$

which follows that $d(u)\ge \frac{1}{3}q$.

Since $\kappa \ge m-k+1$ and $m\ge 7k+24$, we have

$$\begin{aligned} 2m\ge \sum _{u\in W}d(u)\ge \frac{1}{3}\kappa |W|\ge \frac{1}{3}(m-k+1)|W|, \end{aligned}$$

that is, $|W|\le \frac{6m}{m-k+1}<7$. Thus, $|W|\le 6$.

Now we can improve the lower bound that $d(u)\ge \frac{1}{3}\kappa$ for $u\in W$. By (7), we obtain

$$\begin{aligned} \big (\kappa -d(u^*)\big )x_{u^*}&=\sum _{v\in N(u^*)}x_v =\sum _{v\in N(u^*)\cap W}x_v+\sum _{v\in N(u^*)\backslash W}x_v\nonumber \\&\le (|W|-1)x_{u^*}+(d(u^*)-|W|+1)\frac{1}{2}x_{u^*}\\&=\frac{1}{2}(d(u^*)+|W|-1)x_{u^*}, \end{aligned}$$

which yields

$$\begin{aligned} d(u^*)\ge \frac{2}{3}\kappa -\frac{1}{3}|W|+\frac{1}{3}\ge \frac{2}{3}\kappa -\frac{5}{3}. \end{aligned}$$

(8)

Assume that $|W|\ge 2$. For a vertex $u\in W\backslash \{u^*\}$, we obtain

$$\begin{aligned} \big (\kappa -d(u)\big )x_{u}&=\sum _{v\in N(u)}x_v =\sum _{v\in N(u)\cap W}x_v+\sum _{v\in N(u)\backslash W}x_v\nonumber \\&\le (|W|-1)x_{u^*}+(d(u)-|W|+1)\frac{1}{2}x_{u^*}\\&=\frac{1}{2}(d(u)+|W|-1)x_{u^*}. \end{aligned}$$

On the other hand, we have $(\kappa -d(u))x_{u}\ge \frac{1}{2}(\kappa -d(u))x_{u^*}$. Hence, $\frac{1}{2}(d(u)+|W|-1)\ge \frac{1}{2}(\kappa -d(u)),$ that is,

$$\begin{aligned} d(u)\ge \frac{\kappa }{2}-\frac{5}{2}. \end{aligned}$$

(9)

Combining (8) and (9), we have

$$\begin{aligned} m+1\ge d(u^*)+d(u)\ge \frac{2}{3}\kappa -\frac{5}{3}+\frac{\kappa }{2}-\frac{5}{2}= \frac{7}{6}\kappa -\frac{25}{6}\ge \frac{7}{6}(m-k+1)-\frac{25}{6}. \end{aligned}$$

Hence, $m\le 7k+24$, which contradicts the fact that $m\ge 7k+25$. Thus, $|W|\le 1$, and so $|W|=1$ since $|W|\ge 1$. $\square$

From Claim 3, we have $W=\{u^*\}$. Thus, for two vertices $u,v\in V(G)\backslash \{u^*\}$, it has $x_u+x_v<x_{u^*}$.

We assert that $d(u^*)=m-k-1$. On the contrary, suppose that $d(u^*)\le m-k-2$. Then, there is an edge, says $u_1u_2\in E(G)$, such that $u^*\notin \{u_1,u_2\}$. Let $G^\prime$ be the graph obtained from G by deleting the edge $u_1u_2$ and attaching a pendent vertex $u_0$ to $u^*$, and ${{{\varvec{x}}}}^\prime$ be a vector with

$$\begin{aligned} x^\prime _w=\left\{ \begin{array}{ll} x_w,&{}\quad \text {if}\ w\in V(G);\\ 0, &{} \quad \text {if}\ w=u_0. \end{array} \right. \end{aligned}$$

Note that $\Vert {{{\varvec{x}}}}^\prime \Vert _2=1$. By (6), we have

$$\begin{aligned} \kappa (G^\prime )-\kappa (G)&\ge \sum _{uv\in E(G^\prime )}(x^\prime _u+x^\prime _v)^2-\sum _{uv\in E(G)}(x_u+x_v)^2\\&=(x_{u^*}+0)^2-(x_{u_1}+x_{u_2})^2>0. \end{aligned}$$

Since $K_{1,m-k}\not \subseteq G^\prime$. This deduces a contradiction to the maximality of G. Thus, we have $d(u^*)=m-k-1$.

For a vertex $u\in V(G)\backslash \{u^*\}$, we have $d(u)\le k+2$. Then, from (7), we have

$$\begin{aligned} \big (\kappa -d(u)\big )x_u=\sum _{v\in N(u)}x_v\le x_{u^*}+(d(u)-1)\frac{1}{2}x_{u^*}, \end{aligned}$$

which follows

$$\begin{aligned} x_u\le \frac{d(u)+1}{2(q-d(u))}x_{u^*}\le \frac{k+3}{2(\kappa -k-2)}x_{u^*}. \end{aligned}$$

(10)

We can further improve the lower bound in (10). Similarly, by (10) we have

$$\begin{aligned} \big (\kappa -d(u)\big )x_u=\sum _{v\in N(u)}x_v\le x_{u^*}+(d(u)-1)\frac{k+3}{2(\kappa -k-2)}x_{u^*}, \end{aligned}$$

which implies

$$\begin{aligned} x_u&\le \left( \frac{1}{\kappa -d(u)}+\frac{d(u)-1}{\kappa -d(u)} \frac{k+3}{2(\kappa -k-2)}\right) \nonumber \\ x_{u^*}&\le \left( \frac{1}{\kappa -k-2}+\frac{(k+1)(k+3)}{2(\kappa -k-2)^2}\right) x_{u^*}. \end{aligned}$$

(11)

Recall that $\kappa \ge m-k+1$ and $d(u^*)=m-k-1$. By (7), we obtain

$$\begin{aligned} 2x_{u^*}\le \big (\kappa -d(u^*)\big )x_{u^*}=\sum _{u\in N(u^*)} x_u\le d(u^*)\left( \frac{1}{\kappa -k-2}+\frac{(k+1)(k+3)}{2(\kappa -k-2)^2}\right) x_{u^*}. \end{aligned}$$

So

$$\begin{aligned} (m-k-1)\left( \frac{1}{\kappa -k-2}+\frac{(k+1)(k+3)}{2(\kappa -k-2)^2}\right) \ge 2. \end{aligned}$$

On the other hand, we may check

$$\begin{aligned} (m-k-1)\left( \frac{1}{\kappa -k-2}+\frac{(k+1)(k+3)}{2(\kappa -k-2)^2}\right)&\le (m-k-1)\left( \frac{1}{m-2k-1}+\frac{(k+1)(k+3)}{2(m-2k-1)^2}\right) \\&=(m-2k-1+k)\left( \frac{1}{m-2k-1}+\frac{(k+1)(k+3)}{2(m-2k-1)^2}\right) \\&=1+\frac{(k^2+6k+3)m-(k^3+9k^2+9k+3)}{2(m-2k-1)^2}\\&<2, \end{aligned}$$

where the last inequality holds due to the fact that $m\ge \frac{1}{2}k^2+6k+3$. This deduces a contradiction.

This completes the proof of Theorem 6.

4 Concluding remarks

For an odd integer n, let $F_n$ be the friendship graph of order n, i.e., the graph obtained from $K_{1,n-1}$ by embedding $\frac{n-1}{2}$ independent edges. Nikiforov [10] showed that if G does not contain $C_4$ then $\rho (G)\le \rho (F_n)$, with equality if and only if $G=F_n$. In the same paper (also see [11]), Nikiforov posed a conjecture that for even n, if G does not contain $C_4$ as a subgraph then $\rho (G)\le \rho (F^\prime _n)$, where $F^\prime _n$ is obtained from $F_{n-1}$ by attaching a new vertex to the unique vertex of maximum degree, with equality if and only if $G=F^\prime _n$. The conjecture was confirmed by Zhai and Wang in [25].

It is easy to check

$$\begin{aligned} \rho (F_n)=\frac{1+\sqrt{4(n-1)+1}}{2}. \end{aligned}$$

Due to a well-known fact that $\rho (G)\ge \frac{2m}{n}$ for a graph G of order n and size m, if G does not contain $C_4$, then we have

$$\begin{aligned} \frac{2m}{n}\le \rho (G)\le \rho (F_n)=\frac{1+\sqrt{4(n-1)+1}}{2}. \end{aligned}$$

That is,

$$\begin{aligned} m\le \frac{n\left( 1+\sqrt{4(n-1)+1}\right) }{4}, \end{aligned}$$

which is a classical upper bound of the Turán number for $C_4$ obtained by Reiman [17].

One can see that from Nikiforov’s result on odd n (resp., Zhai-Wang’s result on even n), if $\rho (G)\ge \rho (F_n)$ (resp., $\rho (G)\ge \rho (F^\prime _n)$), then $C_4\subseteq G$ or $K_{1,n-1}\subseteq G$. Motivated by this property, we provide a natural conjecture in terms of the maximum degree as follows.

Conjecture 4.1

Let $s\ge 1$ be an integer and $n\ge f(s)$, where f(s) is a function on s. If G is a graph of order n and

$$\begin{aligned} \rho (G)\ge \frac{1+\sqrt{4(n-s)+1}}{2}, \end{aligned}$$

then $K_{1,n-s}\subseteq G$ or $C_4\subseteq G$.

Nikiforov’s theorem confirmed Conjecture 4.1 for $s=1.$ Indeed, Conjecture 4.1 provides a spectral method to pursue the Turán number for $C_4$.