2
$\begingroup$

In Graph Theory mainly in Cayley graphs there are four general questions " according to Audery Terras" : 'Suppose A is the adjacency operator of a connected regular (undirected) graph $X$ of degree $k$ (without multiple edges). Let $spec(A)$ denote the spectrum of $ A$, that is, the set of all eigenvalues of $A$. Let $d$ be the diameter of $X$ and $g$ be the girth.

Question 1. Is $X$ Ramanujan, that is, if $λ ∈spec(A)$, $|λ|≠k$ does $λ$ satisfy $|λ|≤ 2(k-1)^{1/2}$?

Question 2. Is $0∈ spec(A)$ or, equivalently, is $A$ invertible?

Question 3. Can we bound the diameter $d$?

Question 4. Can we bound the girth $g$?

As I am new in this field of mathematics, my question is: are there more important or maybe new questions that researcher can ask or for example analogue some questions?

1 Answers 1

6

Ramanujan graphs are important and interesting and, so far, all examples are constructed as Cayley graphs. If you're interested in Ramanujan graphs, then the problems that Audrey Terras lists are central. But Cayley graphs appear all over graph theory and, when they do, raise questions not on her list.

One famous open problem is whether every Cayley graph has a Hamiltonian path. (There are many variants, all of which are open.) In quantum information theory, we would like to know which Cayley graphs admit perfect state transfer, even just for Cayley graphs of abelian groups. There is active work on the structure of the automorphism groups of Cayley graphs, particularly circulants.