Bounds on graph eigenvalues. I (Q861032): Difference between revisions

The author obtains bounds on the spectral radius of a graph \(G\) and for some eigenvalues of the Laplacian of \(G\). Let \(G=(V,E)\) be a graph of order \(n\). For \(v \in V\), the degree of \(v\) is \(d(v)=| N(v)| \), where \(N(v)\) is the set of vertices adjacent to \(v\). The maximum degree of \(G\) is \(\Delta(G)=\max\{d(v) : v \in V \}\). The author denotes \(\mu(G)=\mu_1(G) \geq \cdots \geq \mu_n(G)\) the eigenvalues of the adjacency matrix of \(G\) and \(0=\lambda_1(G) \leq \cdots \leq \lambda_n(G)=\lambda(G)\) the eigenvalues of the Laplacian matrix of \(G\). Given a graph \(G\), a set \(X \subset V\) is called dominating, if \(N(v) \cap X \neq \emptyset\) for every \(v \in V \backslash X\). The number \(\gamma(G)=\min\{| X| : X\) is a dominating set\} is called the dominating number of \(G\). The main results of the paper establish that if \(G\) is a graph of order \(n \geq 2\) with maximum degree \(\Delta\), and girth at least 5, then \(\mu(G) \leq \min \{\Delta,\sqrt{n-1} \}\). Also, if \(G\) is a graph of order \(n \geq 2\), with dominanting number \(\gamma(G)=\gamma\), then \(\lambda_2(G) \leq n\) if \(\gamma=1\), \(\lambda_2(G) \leq n-\gamma\) if \(\gamma \geq 2\) and \(\lambda_n(G) \geq [n/\gamma]\). The author obtains necessary and sufficient conditions for equality in the above expressions.