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..



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy