Normalized rational semiregular graphs

Abstract

Let G be a graph and let A and D be the adjacency matrix of G and diagonal matrix of vertex degrees of G respectively. If each vertex degree is positive, then the normalized adjacency matrix of G is \hat{A} = D^(â1/2)AD^(â1/2). A classification is given of those graphs for which the all eigenvalues of the normalized adjacency matrix are integral. The problem of determining those graphs G for which \lambda \in Q for each eigenvalue of \hat{A}(G) is considered. These graphs are called normalized rational. It will be shown that a semiregular bipartite graph G with vertex degrees r and s is normalized rational if and only if every eigenvalue of A is a rational multiple of (rs)^{1/2}. This result will be used to classify the values of n for which the semiregular graph (with vertex degrees 2 and n â 1) obtained from subdividing each edge of K_n is normalized rational. Necessary conditions for the k-uniform complete hypergraph on n vertices to be normalized rational are also given. Finally, conditions for the incidence graphs of Steiner triple and quadruple systems to be normalized rational are given.