Algebraic Graph Theory-Shivaramakrishna Pragada

adjacency matrix is irreducible. For every irreducible graph G, we show that each eigenvector of its adjacency matrix has pairwise distinct, non-zero entries.

More generally, consider a graph G whose characteristic polynomial factors over Q as φ_G(λ) = p_1(λ)· · · p_k(λ), where the polynomials p_i(λ) are distinct irreducible factors. For any eigenvalue θ with minimal polynomial p_j (λ), we prove a structure theorem of eigenspaces corresponding each polynomial p_j (λ). We derive a lower bound on the number of distinct entries that must appear in every eigenvector corresponding to θ.

It is conjectured that almost all graphs have irreducible characteristic polynomials, this has recently been confirmed under the assumption of the Extended Riemann Hypothesis. We pose new structural questions about irreducible graphs and present preliminary progress toward understanding their eigenvectors and spectral properties.