Spectral graph theory of the Hypercube

Abstract

In Graph Theory, every graph can be expressed in terms of certain real, symmetric matrices derived from the graph, most notably the adjacency or Laplacian matrices. Spectral Graph Theory focuses on the set of eigenvalues and eigenvectors, called the spectrum, of these matrices and provides several interesting areas of study. One of these is the inverse eigenvalue problem of a graph, which tries to determine information about the possible eigenvalues of the real symmetric matrices whose pattern of nonzero entries is described by a given graph. A second area is the energy of a graph, defined to be the sum of the absolute values of the eigenvalues of the adjacency matrix of that graph. Here we explore these two areas for the hypercube Qn, which is formed recursively by taking the Cartesian product of Qn-1 with the complete graph on two vertices, K2. We analyze and compare several key ideas from the inverse eigenvalue problem for Qn, including the maximum multiplicity of possible eigenvalues, the minimum rank of possible matrices, and the number of paths that occur both as induced subgraphs and after deleting certain vertices. We conclude by deriving several equations for the energy of Qn.