In a recent paper, Caro, Lauri, Mifsud, Yuster, and Zarb ask which parameters $r$ and $c$ admit the existence of an $r$-regular graph such that the neighborhood of each vertex induces exactly $c$ edges. They show that every $r$ with $c$ satisfying $0\leq c\leq { r\choose 2}-5r^{ 3/2}$ is achievable, but no $r$ with $c$ satisfying ${ r\choose 2}-\lfloor\frac{ r}{ 3}\rfloor\leq c\leq { r\choose 2}-1$ is. We strengthen the bound in their nonexistence result from ${ r\choose 2}-\lfloor\frac{ r}{ 3}\rfloor$ to ${ r\choose 2}-\lfloor\frac{ r-2}{ 2}\rfloor$. Additionally, when the graph is the Cayley graph of an abelian group, we obtain a much more fine-grained characterization of the achievable values of $c$ between $\binom{ r}{ 2} - 5r^{ 3/2}$ and $\binom{ r}{ 2} - \lfloor\frac{ r-2}{ 2}\rfloor$, which we conjecture to be the correct answer for general graphs as well. That result relies on a lemma about approximate subgroups in the "99% regime," quantifying the extent to which nearly-additively-closed subsets of an abelian group must be close to actual subgroups. Finally, we consider a generalization to graphs with multiple types of edges and partially resolve several open questions of Caro et al. about $\textit{ flip}$ colorings of graphs.
Categories: math.CO cs.DM