×

Quartic integral Cayley graphs. (English) Zbl 1328.05090

Authors’ abstract: We give exhaustive lists of connected 4-regular integral Cayley graphs and connected 4-regular integral arc-transitive graphs. An integral graph is a graph for which all eigenvalues are integers. A Cayley graph Cay(\(\Gamma , S\)) for a given group \(\Gamma\) and connection set \(S \subset \Gamma\) is the graph with vertex set \(\Gamma\) and with \(a\) connected to \(b\) if and only if \(ba^{-1} \in S\). Up to isomorphism, we find that there are 32 connected quartic integral Cayley graphs; 17 of which are bipartite. Many of these can be realized in a number of different ways by using non-isomorphic choices for \(\Gamma\) and/or \(S\). A graph is arc-transitive if its automorphism group acts transitively upon ordered pairs of adjacent vertices. Up to isomorphism, there are 27 quartic integral graphs that are arc-transitive. Of these 27 graphs, 16 are bipartite and 16 are Cayley graphs. By taking quotients of our Cayley or arc-transitive graphs we also find a number of other quartic integral graphs. Overall, we find 9 new spectra that can be realised by bipartite quartic integral graphs.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C40 Connectivity

Software:

nauty; GAP; GRAPE
PDFBibTeX XMLCite
Full Text: DOI