Spectral graph theory of the Hypercube
Florkowski, Stanley F.
Rasmussen, Craig W.
Gera, Ralucca M.
MetadataShow full item record
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.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Gragg, William B.; Ammar, Gregory S.; Reichel, Lother (Monterey, California. Naval Postgraduate School, 1988-11); NPS-53-89-005We consider the numerical construction of a unitary Hessenberg matrix from spectral data using an inverse QR algorithm. Any unitary upper Hessenberg matrix H with nonnegative subdiagonal elements can be represented by 2n ...
Gragg, William B.; Reichel, Lother (Monterey, California. Naval Postgraduate School, 1989-02); NPS-53-89-007Let H epsilon C be a unitary upper Hessenberg matrix whose eigenvalues, and possibly also eigenvectors, are to be determined. We describe how this eigenproblem can be solved by a divide and conquer method, in which the ...
Fargues, Monique P. (Monterey, California. Naval Postgraduate School, 1990-12); NPS-62-90-016We present easily computable bounds on the extreme generalized eigenvalues of Hermitian pencils (R,B) with finite eigenvalues and positive definite B matrices. The bounds are derived in terms of the generalized eigenvalues ...