On $(r,c)$-constant, planar and circulant graphs

This paper concerns $(r,c)$-constant graphs, which are $r$-regular graphs in which the subgraph induced by the open neighbourhood of every vertex has precisely $c$ edges. The family of $(r,c)$-graphs contains vertex-transitive graphs (and in particular Cayley graphs), graphs with constant link (sometimes called locally isomorphic graphs), $(r,b)$-regular graphs, strongly regular graphs, and much more. This family was recently introduced in [arXiv:2312.08777] serving as important tool in constructing flip graphs [arXiv:2312.08777, arXiv:2401.02315]. In this paper we shall mainly deal with the following: i. Existence and non-existence of $(r,c)$-planar graphs. We completely determine the cases of existence and non-existence of such graphs and supply the smallest order in the case when they exist. ii. We consider the existence of $(r,c)$-circulant graphs. We prove that for $c\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}3)$ no $(r,c)$-circulant graph exists and that for $c\equiv 0,1(\mathrm{m}\mathrm{o}\mathrm{d}3)$, $c>0$ and $r\ge 6+\sqrt{\frac{8c-5}{3}}$ there exists $(r,c)$-circulant graphs. Moreover for $c=0$ and $r\ge 1$, $(r,0)$-circulants exist. iii. We consider the existence and non-existence of small $(r,c)$-constant graphs, supplying a complete table of the smallest order of graphs we found for $0\le c\le \left(\genfrac{}{}{0px}{}{r}{2}\right)$ and $r\le 6$. We shall also determine all the cases in this range for which $(r,c)$-constant graphs don’t exist. We establish a public database of $(r,c)$-constant graphs for varying $r$, $c$ and order.