Eigenvalue −1 of the Vertex Quadrangulation of a 4-Regular Graph

Abstract

The vertex quadrangulation QG of a 4-regular graph G visually looks like a graph whose vertices are depicted as empty squares, and the connecting edges are attached to the corners of the squares. In a previous work [JOMC 59, 1551–1569 (2021)], the question was posed: does the spectrum of an arbitrary unweighted graph QG include the full spectrum {3,(−1)3} of the tetrahedron graph (complete graph K4)? Previously, many bipartite and nonbipartite graphs QG with such a subspectrum have been found; for example, a nonbipartite variant of the graph QK5. Here, we present one of the variants of the nonbipartite vertex quadrangulation QO of the octahedron graph O, which has eigenvalue (−1) of multiplicity 2 in the spectrum, while the spectrum of the bipartite variant QO contains eigenvalue (−1) of multiplicity 3. Thus, in the case of nonbipartite graphs, the answer to the question posed depends on the particular graph QG. Here, we continue to explore the spectrum of graphs QG. Some possible connections of the mathematical theme to chemistry are also noted.

Keywords

• vertex quadrangulation
• truncation
• characteristic polynomial
• graph spectrum
• (matrix, graph) divisor
• equitable partition