MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In graph theory, an edge regular graph is defined as follows. Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be edge regular if there is also integer λ such that:

Every two adjacent vertices have λ common neighbors.

A graph of this kind is sometimes said to be an er(v,k,λ).

I want know about eigenvalues of edge regular graph, how can we find eigenvalue of this graph?

share|cite|improve this question
It is clear that one eigenvalue is k. I would not expect that the parameters (v,k,λ) alone determine the other eigenvalues. – Tsuyoshi Ito Aug 23 '10 at 11:41

In the event that every non adjacent pair has a fixed number $\mu$ of common neighbors this is a strongly regular graph srg$(v,k,\lambda,\mu)$ for which the 3 distinct eigenvalues and their multiplicities are known: (in this case the graph is diameter 2 or a disjoint union of isomorphic complete graphs.) An erg with k=2 and $\lambda=0$ is a disjoint union of cycles (none of length 3) and could have a wide range of eigenvalues. If you want connected then with v=12 k=3 and $\lambda=0$ you could have a wide variety of graphs obtained by connecting each point to three others without creating triangles (such as the skeleton of a dodecahedron, or of a hexagonal prism) all would have 3 as the unique largest eigenvalue but the rest of the spectrum could be many things.

share|cite|improve this answer

For the special case when every two non-adjacent vertices have exactly c1 or c2 neighbours, there are some eigenvalue bounds in my paper:

share|cite|improve this answer

Your Answer


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.