Projects per year
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(Γ, S) for a given group Γ and connection set S ⊂ Γ is the graph with vertex set Γ and with a connected to b if and only if ba−1 ∈ 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 on the 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.
Original language | English |
---|---|
Pages (from-to) | 381-408 |
Number of pages | 28 |
Journal | Ars Mathematica Contemporanea |
Volume | 8 |
Issue number | 2 |
Publication status | Published - 2015 |
Keywords
- Graph spectrum
- integral graph
- Cayley graph
- arc-transitive
- vertex-transitive bipartite double cover
- voltage assignment
- graph homomorphism
Projects
- 1 Finished
-
Extremal Problems in Hypergraph Matchings
Wanless, I., Greenhill, C. & Aharoni, R.
Australian Research Council (ARC), University of New South Wales (UNSW)
3/01/12 → 31/12/14
Project: Research