What does the eigenvalue of a graph mean? I know how to compute the eigenvalues from the adjacency matrix representation of a graph but am interested in its physical significance.
If two graphs have different eigenvalues then they cannot be isomorphic. is there any other use cases of eigenvalues in the graph.
If a $d$-regular graph $G$ is such that the second-largest eigenvalue $\lambda$ of $A(G)$ is significantly smaller than $d$ i.e., $d-\lambda = \Omega(1)d$, then the graph is a good expander--all sets $S$ with no more than half the number of vertices in them have $\Omega(|S|)$ neighbours outside. So to bisect the graph, many vertices would have to be removed, even for $d =3$. The dual properties of being both sparse and having high bisection width mmakes these graphs of interest to computer scientists in designing good algorithms.