Article in press
Authors:
Title:
Number of cliques of Paley-type graphs over finite commutative local rings
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-08-22 , Revised: 2024-01-20 , Accepted: 2024-01-25 , Available online: 2024-02-08 , https://doi.org/10.7151/dmgt.2538
Abstract:
In this work, given $(R,\frak{m})$ a finite commutative local ring with identity
and $k \in \mathbb{N}$ with $(k,|R|)=1$, we study the number of cliques of any size in
the Cayley graph $G_R(k)=Cay(R,U_R(k))$ with $U_R(k)=\{x^k : x\in R^*\}$.
Using the known fact that the graph $G_R(k)$ can be obtained by blowing-up the
vertices of $G_{\mathbb{F}_{q}}(k)$ a number $|\frak{m}|$ of times, we reduce the study
of the number of cliques in $G_R(k)$ over the local ring $R$ to the computation
of the number of cliques of $G_{R/\frak{m}}(k)$ over the finite residue field
$R/\frak{m} \simeq \mathbb{F}_q$. In this way, using known numbers of $\ell$-cliques
of generalized Paley graphs ($k=2,3,4$ and $\ell=3,4$), we obtain several
explicit results for the number of $\ell$-cliques over finite commutative local
rings with identity.
Keywords:
local rings, generalized Paley graphs, cliques
References:
- R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jiménez, R. Karpman, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin. 16(1) (2009) #R117.
https://doi.org/10.37236/206 - W. Ananchuen, On the adjacency properties of generalized Paley graphs, Australas. J. Combin. 24 (2001) 129–147.
- W. Ananchuen and L. Cacceta, Cubic and quadruple Paley graphs with the n-e.c. property, Discrete Math. 306 (2006) 2954–2961.
https://doi.org/10.1016/j.disc.2006.03.073 - R. Atanasov, M. Budden, J. Lambert, K. Murphy and A. Penland, On certain induced subgraphs of Paley graphs, Acta Univ. Apulensis Math. Inform. 40 (2014) 51–65.
https://doi.org/10.17114/j.aua.2014.40.05 - N. de Beaudrap, On restricted unitary Cayley graphs and symplectic transformations modulo $n$, Electron. J. Combin. 17 (2010) #R69.
https://doi.org/10.37236/341 - A. Bhowmik and R. Barman, On a Paley-type graph on $\mathbb{Z}_n$, Graphs Combin. 38 (2022) 41.
https://doi.org/10.1007/s00373-021-02426-2 - A. Bhowmik and R. Barman, Cliques of orders three and four in the Paley-type graphs (2023).
arXiv: 2301.07021 - D.A. Cox, Primes of the Form $x^2+n y^2$ (John Wiley & Sons, Inc., 1989).
- A. Das, Paley-type graphs of order a product of two distinct primes, Algebra Discrete Math. 28 (2019) 44–59.
- M.L. Dawsey and D. McCarthy, Generalized Paley graphs and their complete subgraphs of orders three and four, Res. Math Sci. 8 (2021) 18.
https://doi.org/10.1007/s40687-021-00254-7 - R.J. Evans, J.R. Pulham and J. Sheehan, On the number of complete subgraphs contained in certain graphs, J. Combin. Theory Ser. B 30 (1981) 364–371.
https://doi.org/10.1016/0095-8956(81)90054-X - P. Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Kőzl 7 (1962) 459–464.
- J. Greene, Hypergeometric functions over finite fields, Trans. Amer. Math. Soc. 301 (1987) 77–101.
https://doi.org/10.1090/S0002-9947-1987-0879564-8 - R.E. Greenwood and A.M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955) 1–7.
https://doi.org/10.4153/CJM-1955-001-4 - A. Ilić, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009) 1881–1889.
https://doi.org/10.1016/j.laa.2009.06.025 - G.A. Jones, Paley and the Paley graphs, in: Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, WAGT 2016, Springer Proceedings in Mathematics & Statistics, 305, (Springer, Cham. 2020) 155–183.
- T.K. Lim and C.E. Praeger, On generalised Paley graphs and their automorphism groups, Michigan Math. J. 58 (2009) 294–308.
https://doi.org/10.1307/mmj/1242071694 - X. Liu and S. Zhou, Spectral properties of unitary Cayley graphs of finite commutative rings, Electron. J. Combin. 19(4) (2012) #P13.
https://doi.org/10.37236/2390 - X. Liu and S. Zhou, Quadratic unitary Cayley graphs of finite commutative rings, Linear Algebra Appl. 479 (2015) 73–90.
https://doi.org/10.1016/j.laa.2015.03.037 - R.A. Podestá and D.E. Videla, The Waring's problem over finite fields through generalized Paley graphs, Discrete Math. 344(5) (2021) 112324.
https://doi.org/10.1016/j.disc.2021.112324 - R.A. Podestá and D.E. Videla, Integral equienergetic non-isospectral unitary Cayley graphs, Linear Algebra Appl. 612 (2021) 42–74.
https://doi.org/10.1016/j.laa.2020.12.001 - R.A. Podestá and D.E. Videla, A reduction formula for Waring numbers through generalized Paley graphs, J. Algebraic Combin. 56 (2022) 1255–1285.
https://doi.org/10.1007/s10801-022-01154-x - R.A. Podestá and D.E. Videla, Generalized Paley graphs equienergetic with their complements, Linear Multilinear Algebra (2022) , in press.
https://doi.org/10.1080/03081087.2022.2159918 - R.A. Podestá and D.E. Videla, Waring numbers over finite commutative local rings, Discrete Math. 346(10) (2023) 113567.
https://doi.org/10.1016/j.disc.2023.113567 - D.E. Videla, On diagonal equations over finite fields via walks in NEPS of graphs, Finite Fields App. 75 (2021) 101882.
https://doi.org/10.1016/j.ffa.2021.101882 - C.H. Yip, On the directions determined by Cartesian products and the clique number of generalized Paley graphs, Integers 21 (2021) A51.
- C.H. Yip, On the clique number of Paley graphs of prime power order, Finite Fields Appl. 77 (2022) 101930.
https://doi.org/10.1016/j.ffa.2021.101930
Close