On the sum of the first two largest signless Laplacian eigenvalues of a graph¹¹1 Corresponding author Email: [email protected] (C.-X. He).
This research is supported by National Natural Science Foundation of China (No.12271362).

Assume that $G$ is a counterexample with a minimum possible number of edges. By Corollary 2.2, we have $e(G)\leq S_{k}(G)\leq S_{k}(H)+S_{k}(G-H)$. This implies that $S_{k}(G-H)\geq e(G-H)$, since $e(G)\geq e(H)+e(G-H)$ and $S_{k}(H)\leq e(H)$, which contradicts the minimality of $e(G)$. ∎

For $i=1,\ldots,n$, define $\sigma_{i}=q_{i}(G^{\prime})-q_{i}(G)$. By Lemma 2.9, $\sigma_{i}\geq 0$, for any $i$. Let $d_{1}\geq\cdots\geq d_{n}$ and $d_{1}^{\prime}\geq\cdots\geq d_{n}^{\prime}$ be vertex degrees of $G$ and $G^{\prime}$, respectively. Recall that for any graph $H$, considering the trace of the matrix $Q^{2}(H)$, we have

Applying this fact, we have

This yields that

Since $q_{k}(G)\geq d(u)+d(v)+2$, $S_{k}(G^{\prime})-S_{k}(G)=\sum^{k}_{i=1}\sigma_{i}<1$, and the result follows. ∎

The graph $G$ has an obvious partition $G=\bigvee_{H}\{G_{1},G_{2},G_{3}\}$, and the corresponding quotient matrix is

By Lemma 2.1 and direct calculation, the characteristic polynomial of $Q(G)$ is

The 2-th additive compound matrix of $Q^{\pi}$ is

and its characteristic polynomia is $P(\Delta_{2}(Q^{\pi}),x)=x^{3}-(6+2n)x^{2}+(n^{2}+9n+9)x-3n^{2}-9n+4$. By direct calculation we obtain

Since $q_{2}\geq 2$, by Lemma 2.9, $P(Q^{\pi},x)$ contains the largest two roots of $P_{Q}(G,x)$. From Corollary 2.1 and the fact that $e(G)=n$, we have $\frac{1.3}{n}<f(G)<\frac{1.5}{n}$. ∎

Let $n=|V(G)|$. Since $m(G)=1$, it is easy to check that either $G=K_{1,k-1}\cup(n-k)K_{1}$ for some $k$, $1\leq k\leq n$ or $G=K_{3}\cup(n-3)K_{1}$. By Lemma 2.7, the assertion holds. ∎

We may assume that $G$ is a connected graph with at least 11 vertices. First suppose that $G$ has no $K_{3}$ as a subgraph, if $G$ is a tree, by Corollary 2.4, we have $f(G)>\frac{1.5}{n}$. Since $m(G)=2$, $G$ is isomorphic to $G_{5}$ in Fig. 1, using the 2-th additive compound matrix approach, we have $f(G)>0.5>\frac{1.5}{n}$, details are deferred in the Appendix.

Next suppose that $G$ has a subgraph $H=K_{3}$ with $V(H)=\{u,v,w\}$.

If every edge of $G$ has at least one endpoint in $V(H)$, since $m(G)=2$, we only need to consider $q(G)=0,1$ and 2, respectively. Then $G$ is isomorphic to $G_{1}\ (1\leq t_{1}\leq n-2,\ 0\leq t_{2},\ t_{3}\leq n-3)$ or $G_{2}\ (7\leq t=n-4)$ in Fig. 1.

If there exists an edge $e=ab$ has no endpoint in $V(H)$, let $M=V(G)-\{a,b,u,v,w\}$, since $m(G)=2$, $M$ is an independent set and $e(V(H),M)=0$, and all vertices in $M$ are adjacent to one of the endpoints of $e$, say $a$. Hence there are no edges between $b$ and $V(H)$, we only need to consider $|N(a)\cap V(H)|=1$ and 3, respectively (isomorphic to $G_{2}$ when $|N(a)\cap V(H)|=2$). Then $G$ is isomorphic to $G_{3}\ (7\leq t=n-4)$ or $G_{4}\ (7\leq t=n-4)$ in Fig. 1.

When $G\cong G_{1}$, let $V(\overline{K_{t_{i}}})=\{v_{1},\ldots,v_{t_{i}}\}$ $(i=1,2,3)$, and $G_{t_{1},t_{2},t_{3}}$ be a graph of order $n$ $(n=t_{1}+t_{2}+t_{3})$, which consists of three independent sets $\overline{K_{t_{i}}}$ $(i=1,2,3)$, where $t_{1}$ triangles share one common edge and $t_{2},t_{3}$ pendant vertices at each end of the common edge. The graph $G_{t_{1},t_{2},t_{3}}$ has an obvious partition $G=\bigvee_{H}\{G_{1},G_{2},...,G_{k}\}(k=5)$ where the corresponding quotient matrix is

By Lemma 2.1 and direct calculation, the characteristic polynomial of $Q(G_{t_{1},t_{2},t_{3}})$ is

Without loss of generality, we may assume $t_{2}\geq t_{3}$. Let

By direct computation, $P_{1}-P_{2}$ is always positive (details are deferred in the Appendix), which indicates the largest root of $P_{1}$ less than the largest root of $P_{2}$.

Since $q_{2}>2$, by Lemma 2.9 (if $t_{1}=1$ and $t_{3}=0$, the previous results (see Theorem 2.4 in [2]) verify that $q_{2}>3-\frac{2.5}{n}>2$), $P(Q^{\pi}(G_{t_{1},t_{2},t_{3}},x))$ and $P(Q^{\pi}(G_{t_{1},t_{2}+1,t_{3}-1},x))$ contain the largest two roots of $P_{Q}(G_{t_{1},t_{2},t_{3}},x)$ and $P_{Q}(G_{t_{1},t_{2}+1,t_{3}-1},x)$. By Corollary 2.1, we have $f(G_{t_{1},t_{2},t_{3}})>f(G_{t_{1},t_{2}+1,t_{3}-1})$. By recursive relationships, we have $f(G_{1})>f(G_{1}^{1})$.

Let $G_{t_{1},t_{2}}$ be a graph of order $n$ $(n=t_{1}+t_{2})$, which consists of two independent sets $\overline{K_{t_{i}}}$ $(i=1,2)$, where $t_{1}$ triangles share one common edge and $t_{2}$ pendant vertices at the end of the common edge. Let

By using computer computations, $P_{3}-P_{4}$ is always positive (details are deferred in the Appendix), which indicates the largest root of $P_{3}$ less than the largest root of $P_{4}$.

Since $q_{2}>2$, by Lemma 2.9 (if $t_{1}=1$, the previous results (see Theorem 2.4 in [2]) verify that $q_{2}>3-\frac{2.5}{n}>2$), $P(Q^{\pi}(G_{t_{1},t_{2}},x))$ and $P(Q^{\pi}(G_{t_{1}-1,t_{2}+1},x))$ contains the largest two roots of $P_{Q}(G_{t_{1},t_{2}},x)$ and $P_{Q}(G_{t_{1}-1,t_{2}+1},x)$. By Corollary 2.1, we have $f(G_{t_{1},t_{2}})>f(G_{t_{1}-1,t_{2}+1})$. By recursive relationships, we have $f(G_{1}^{1})>f(G_{1}^{2})$. Then $f(G_{1})>f(G_{1}^{1})>f(G_{1}^{2})=f(K^{+}_{1,n-1})$.

When $G\cong G_{2}$, the graph $G$ has an obvious partition $G=\bigvee_{H}\{G_{1},G_{2},...,G_{k}\}(k=4)$ where the corresponding quotient matrix is

By Lemma 2.1 and direct calculation, the characteristic polynomial of $Q(G)$ is

By simple calculations we obtain

with $g(t)=(t^{2}+5.3t+8.9)(t+5.2)(t+4.6)(t+4.3)(t+1.3)(t-6.9)$, which indicates $q_{1}(G)<t+3.25-\frac{1.5}{t+4}$ and $q_{2}(G)<4.75$, then $S_{2}(G)<t+8-\frac{1.5}{t+4}=e(G)+3-\frac{1.5}{n}$, we have $f(G)>\frac{1.5}{n}$.

When $G\cong G_{3}$, we use the quotient matrix approach, when $G\cong G_{4}$, we use the 2-th additive compound matrix approach, details are deferred in the Appendix. This completes the proof.

∎

Without loss of generality, we may suppose that $e_{1}=a_{1}b_{1}$, $e_{2}=a_{2}b_{2}$ and $e_{3}=a_{3}b_{3}$ are three independent edges in $G$.

We first suppose that $G$ contains $K_{3}\cup 2K_{2}$ as a subgraph and $V(K_{3})=\{a_{1},b_{1},u\}$. Let $V_{1}=V(K_{3}\cup 2K_{2})$, $M^{\prime}=V(G)-V_{1}$. Then $|M^{\prime}|\geq 4$. Since $m(G)=3$, $M^{\prime}$ is an independent set and $e(V(K_{3}),M^{\prime})=0$. Since $G$ has neither $3K_{1,2}$ nor $4K_{2}$ as a subgraph and $|M^{\prime}|\geq 4$, there exists exactly one vertex $a_{3}$ (w.l.o.g.) which is adjacent to vertices of $M^{\prime}$ and $d(b_{3})=1$.

Let $V_{2}=\{a_{1},b_{1},u,a_{2},b_{2}\}$, $E_{1}=\{a_{3}w|w\in V_{2}\}$. Then $G[E_{1}]$ is a star with center $a_{3}$, and $G-E_{1}$ is a disjoint union of a star $K_{1,|M^{\prime}|+1}$ with center $a_{3}$ and a graph $G[V_{2}]$ containing $K_{3}+K_{2}$.

If $G[V_{2}]$ is connected, then $G[V_{2}]$ is spanning subgraph of $K_{5}$ which contains $K_{3}\cup K_{2}$ as a subgraph, by direct calculation, we have $q_{1}(G[V_{2}])<e(G[V_{2}])-0.15<e(G[V_{2}])-\frac{1.5}{n}\ (n\geq 11)$. Since $n(K_{1,|M^{\prime}|+1})\geq 6$, so $q_{2}(G[V_{2}])\leq q_{2}(K_{5})<q_{1}(K_{1,|M^{\prime}|+1})$. Hence $S_{2}(G-E_{1})=q_{1}(G[V_{2}])+q_{1}(K_{1,|M^{\prime}|+1})<e(G[V_{2}])-\frac{1.5}{n}+e(K_{1,|M^{\prime}|+1})+1=e(G-E_{1})+1-\frac{1.5}{n}$. Thus by Corollary 2.2, $S_{2}(G)\leq S_{2}(G[E_{1}])+S_{2}(G-E_{1})<e(G[E_{1}])+2+e(G-E_{1})+1-\frac{1.5}{n}=e(G)+3-\frac{1.5}{n}$, we have $f(G)>\frac{1.5}{n}$.