Article in volume
Authors:
Title:
On $(r,c)$-constant, planar and circulant graphs
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 707-723
Received: 2024-03-12 , Revised: 2024-06-14 , Accepted: 2024-06-14 , Available online: 2024-07-03 , https://doi.org/10.7151/dmgt.2551
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 \cite{caro2023, mifsud2024}.
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 \equiv \mod{2}{3}$ no $(r,c)$-circulant graph exists and that for $c \equiv \mod{0, 1}{3}$, $c > 0$ and $r \geq 6 + \sqrt{\frac{8c - 5}{3}}$ there exist $(r,c)$-circulant graphs. Moreover for $c = 0$ and $r \geq 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 \leq c \leq \binom{r}{2}$ and $r \leq 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.
Keywords:
planar graphs, circulants
References:
- A. Ali, G. Chartrand and P. Zhang, On link-irregular graphs, Discuss. Math. Graph Theory 45 (2025) 95–-110.
https://doi.org/10.7151/dmgt.2521 - J. Anderson, A. Dhawan, and A. Kuchukova, Coloring locally sparse graphs (2024).
arXiv: 2402.19271 - G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007) 323–357.
- A.E. Brouwer, Some locally Kneser graphs (2023).
arXiv: 2312.02964 - A.E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs (Cambridge University Press, Cambridge, 2022).
https://doi.org/10.1017/9781009057226 - Y. Caro, J. Lauri, X. Mifsud, R. Yuster and C. Zarb, Flip colouring of graphs (2023).
arXiv: 2312.08777 - Y. Caro and X. Mifsud, The $(r,c)$-graph database (2024).
https://rcgraphs.research.um.edu.mt - M. Conder, J. Schillewaert and G. Verret, Parameters for certain locally-regular graphs (2021).
arXiv: 2112.00276 - T. Dobson, A. Malnič and D. Marušič, Symmetry in Graphs (Cambridge University Press, Cambridge, 2022).
https://doi.org/10.1017/9781108553995 - I. Fabrici and T. Madaras, The structure of $1$-planar graphs, Discrete Math. 307 (2007) 854–865.
https://doi.org/10.1016/j.disc.2005.11.056 - F. Harary, Graph Theory (3rd Ed.) (Addison-Wesley Publishing Company, 1972).
- J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction (2nd Ed.) (Cambridge University Press, Cambridge, 2016).
https://doi.org/10.1017/CBO9781316669846 - B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112.
https://doi.org/10.1016/j.jsc.2013.09.003 - X. Mifsud, Flip colouring of graphs II (2024).
arXiv: 2401.02315 - B.R. Nair and A. Vijayakumar, About triangles in a graph and its complement, Discrete Math. 131 (1994) 205–210.
https://doi.org/10.1016/0012-365X(94)90385-9 - B.R. Nair and A. Vijayakumar, Strongly edge triangle regular graphs and a conjecture of Kotzig, Discrete Math. 158 (1996) 201–209.
https://doi.org/10.1016/0012-365X(95)00077-A - D. Stevanović, M. Ghebleh, G. Caporossi, A. Vijayakumar and S. Stevanović, Searching for regular, triangle-distinct graphs (2024).
arXiv: 2401.10971 - D.B. West, Introduction to Graph Theory (2nd Ed.) (Prentice Hall, 2001).
- Wolfram Research (2007), Graph Data, Wolfram Language function (updated 2023).
https://reference.wolfram.com/language/ref/GraphData.html - X. Yu, Z. Shao and Z. Li, On the classification and dispersability of circulant graphs with two jump lengths, Available at SSRN (2023).
https://doi.org/10.2139/ssrn.4589642
Close