Quartic integral Cayley graphs - Minchenko, Marsha (Ars mathematica contemporanea, 2015)
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 ?$\text{Cay}(Γ, S)$? for a given group ?$Γ$? and connection set ?$S \subset Γ$? is the graph with vertex set ?$Γ$? 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 ?$Γ$? and/or different choices for ?$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.
Keywords: arc-transitive; Cayley graph; Cayleyev graf; celoštevilski graf; graph homomorphism; graph spectrum; homomorfizem grafov; integral graph; ločno-tranzitiven; prirejanje napetosti; spekter grafa; vertex-transitive bipartite double cover; voltage assignment; vozliščno tranzitiven dvodelen dvojni krov