Normalized Laplacian eigenvalues with chromatic number and independence number of graphs

ABSTRACT

Let ${\rho }_1\ge {\rho }_2\ge \cdots \ge {\rho }_{n-1}\ge {\rho }_n=0$ be the normalized Laplacian eigenvalues of a graph G with n vertices. Also, let χ and α be the chromatic number and the independence number of a graph G, respectively. In this paper, we discuss some properties of graphs with ${\rho }_1=\chi /\left(\chi -1\right)$. In particular, we characterize all the graphs with ${\rho }_1=\chi /\left(\chi -1\right)$ when the maximum degree is n−1. Moreover, we obtain an upper bound on the multiplicity of normalized Laplacian eigenvalues $m_G\left(\rho \right)$ in terms of n and α, and also characterize graphs for which the bound is attained.

KEYWORDS:

• Normalized Laplacian spectral radius
• multiplicity of normalized Lapalcian eigenvalues
• chromatic number
• independence number

AMS CLASSIFICATIONS:

• 05C50
• 15A18

Acknowledgements

The authors would like to thank the anonymous referee for valuable comments which have considerably improved the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Kinkar Ch. Das is supported by the Sungkyun research fund, Sungkyunkwan University, 2017, and National Research Foundation of the Korean government with grant No. 2017R1D1A1B03028642.