Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.