Nordhaus-Gaddum-type result on the second largest signless Laplacian eigenvalue of a graph

ABSTRACT

Let G be a simple graph of order n with m edges. Denote by $D\left(G\right)$ the diagonal matrix of its vertex degrees and by $A\left(G\right)$ its adjacency matrix. Then the signless Laplacian matrix of G is $Q\left(G\right)=D\left(G\right)+A\left(G\right)$. Let $q_1\ge q_2\ge \cdots \ge q_n$ be the signless Laplacian eigenvalues of graph G and also let $\nu =\nu \left(G\right)$ $(1\le \nu \le n)$ be the largest positive integer such that $q_{\nu }\ge 2m/n$. Denote by $\overline{G}$ the complement graph of graph G. If $G≆K_n,{\overline{K}}_n,K_{n-1}\cup K_1,K_{1,n-1},K_n-e,K_2\cup (n-2)K_1$, then we prove that $q_2\left(G\right)+q_2\left(\overline{G}\right)\ge n-1$. Moreover, if $G≆K_{1,n-1},K_{n-1}\cup K_1,K_n-e,K_2\cup (n-2)K_1$, then $\nu +\overline{\nu }\ge 3$.

KEYWORDS:

• Graph
• The second largest signless Laplacian eigenvalue
• Maximum degree
• Second maximum degree
• Nordhaus-Gaddum-type

AMS CLASSIFICATION:

• 05C50

Acknowledgements

The author would like to thank the referee for his/her valuable comments which lead to an improvement of the original manuscript.

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

The author was supported by the National Research Foundation of the Korean government with grant No. 2017R1D1A1B03028642.