Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

2 Answers

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: http://en.wikipedia.org/wiki/Strongly_regular_graph (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|improve this answer
add comment

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

http://www.tandfonline.com/doi/abs/10.1080/03081080600867210

share|improve this answer
add comment

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.