Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite
1

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
3  
I don't understand what you're asking. If you're given the adjacency matrix, all four of your questions can be answered in small polynomial time using well-known algorithms. – JɛffE Dec 16 '12 at 4:51
It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions. – Kaveh♦ Dec 16 '12 at 19:40

closed as not a real question by JɛffE, Yuval Filmus, Kaveh♦ Dec 16 '12 at 19:40

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.