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

Abstract

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 [6], serving as an important tool in constructing flip graphs [6, 14]. In this paper we shall mainly deals 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 ≡ 2 (mod 3) no (r, c)-circulant graph exists and that for c ≡ 0, 1 (mod 3), c > 0 and r ≥ 6 + √8c−5/3 there exist (r, c)-circulant graphs. Moreover for c = 0 and r ≥ 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 ≤ c ≤ C(r, 2) and r ≤ 6. We shall also determine all the cases in this range for which (r, c)-constant graphs do not exist. We establish a public database of (r, c)-constant graphs for varying r, c and order.