Graph covers with two new eigenvalues

DOI10.1016/J.EJC.2020.103280MaRDI QIDQ2225463zbMATH OpenOpenAlexFDO

Authors Maxwell Levit, Olha Silina, Chris Godsil

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.01221

zbMATH Keywords

sensitivity conjecturetwo-eigenvalue cover

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A certain signed adjacency matrix of the hypercube, which Hao Huang used last year to resolve the sensitivity conjecture, is closely related to the unique, 4-cycle free, 2-fold cover of the hypercube. We develop a framework in which this connection is a natural first example of the relationship between group labeled adjacency matrices with few eigenvalues, and combinatorially interesting covering graphs. In particular, we define a two-eigenvalue cover to be a covering graph whose adjacency spectra differs (as a multiset) from that of the graph it covers by exactly two eigenvalues. We show that walk regularity of a graph implies walk regularity of any abelian two-eigenvalue cover. We also give a spectral characterization for when a cyclic two-eigenvalue cover of a strongly-regular graph is distance regular.

Recommendations

• Eigenvalues of 2-edge-coverings
• Covering automorphisms and some eigenvalues of a graph
• On graphs with exactly two positive eigenvalues
• A complete characterization of graphs with exactly two positive eigenvalues
• On 2-fold covers of graphs
• Covers of Eulerian graphs
• Covers of graphs and EGQs
• Coverings of graphs and maps, orthogonality, and eigenvectors
• On graphs with multiple eigenvalues
• Some results on graphs with exactly two main eigenvalues

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Antipodal covering graphs
• Biased graphs. I: Bias, balance, and gains
• Distance regular covers of the complete graph
• Equiangular lines
• Equiangular lines and covers of the complete graph
• Feasibility conditions for the existence of walk-regular graphs
• Generating all graph coverings by permutation voltage assignments
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Integer symmetric matrices having all their eigenvalues in the interval \([ - 2,2]\)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Lifts, discrepancy and nearly optimal spectral gap
• On generalized hexagons and a near octagon whose lines have three points
• On signed graphs with two distinct eigenvalues
• Open problems in the spectral theory of signed graphs
• Representations and characters of groups.
• Spectra of signed graphs with two eigenvalues
• Voltage graphs

Cited in

(1)

• Pretty good state transfer in discrete-time quantum walks

This page was built for publication: Graph covers with two new eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225463)