2024/03/07 by Yair Caro, Caro, Yair, Xandru Mifsud +1 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2403.04401
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 ≡ 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 exists (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 ≤ \binomr2 and r ≤ 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.