Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I have a question about the relationship between parameters of weakly regular graphs (if it exists)

Consider two weakly regular graphs with parameters $(n,k,\lambda,\beta)$ where n is number of vertices, k is the degree, $\lambda$ is the number of common neighbors of adjacent vertices, and $\beta$ is the number of common neighbors of nonadjacent vertices. (At least one of the latter two parameters $(\lambda,\beta)$ will have two values for a weakly regular graph).

Suppose $(n,k)$ is the same for both graphs. And suppose one graph has $\lambda=0$ for all vertices (zero clustering, triangle-free) and the other one has $\lambda=1$ for all such vertices. Can we say/show that when $\lambda =1$ (or in general higher), the $\beta$ values of the remaining vertices in that graph is lower than the other graph? In other words, the number of common neighbours of nonadjacent vertices is less when the number of common neighbours of adjacent vertices are higher in a graph.

thank you very much in advance..


share|cite|improve this question
Crossposted on mathoverflow: – Yuval Filmus Aug 15 '11 at 20:21

A weaker statement is certainly true. Given two graphs $G_1=(n,k,0,\beta_a\lt\beta_b\le...\beta_i)$ and $G_2=(n,k,1,\beta_\alpha\lt\beta_\beta\lt...\beta_j)$ we can say that the largest $\beta_i\lt$ the largest $\beta_j$ and that the smallest $\beta_i \lt$ the smallest $\beta_j$, because of the extra connectivity induced relative to a selected vertex on its non-adjacent neighbors.

However, there exist weakly regular graphs with $n$ and $k$ equal with different $\lambda$ who share one or more $\beta$ values.

share|cite|improve this answer

Your Answer


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