Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $G$ is said to be strongly regular, defined by four parameters $(n,k,\lambda, \mu)$, if $G$ is a $k$-regular graph of order $n$ such that any two adjacent vertices share $\lambda$ common neighbors and any two non-adjacent vertices share $\mu$ common neighbors.)
Given parameters $(n,k,\lambda, \mu)$, determining the existence (or non-existence) of strongly regular graphs (SRGs) with these parameters is generally a difficult problem. So I am seeking to propose a relaxation of strongly regular graphs called "neighborhood-bounded regular graphs," (NBRGs) wherein instead of requiring that any two adjacent vertices share precisely $\lambda$ common neighbors, we instead simply require that they share at least $\lambda$ common neighbors (i.e., any two adjacent vertices share $\geq \lambda$ common neighbors). Clearly any $\text{SRG}(n,k,\lambda,\mu)$ is an instance of a $\text{NBRG}(n,k,\lambda)$, but the converse needn't be so. It seems plausible to me that the relaxation of strong-regularity in exchange for bounded common neighborhood sizes might afford some easier existence conditions that can be identified for these NBRGs.
As a concrete example question, I was looking at regular circulant graphs and found that it is possible to identify a $\text{NBRG}(24,12,6)$ graph (for those interested, this is the circulant graph on 24 vertices with jumps {1,3,4,5,6,9}). However, I have been unable to identify an $\text{NBRG}(24,12,7)$ graph; does such a graph exist, or is it possible to prove that such a graph doesn't exist?
More generally, we may ask for what values of $(n,k,\lambda)$ can a $\text{NBRG}(n,k,\lambda)$ exist? Any thoughts/references are welcome!
Thank you!
