On a Paley-type graph on ℤ_n

2020/12/17 by Bhowmik, Anwita, Barman, Rupam
#11T24 #11T30 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #Primary: 05C30 #Secondary: 05C55

paper · doi:10.48550/arxiv.2012.09735

Abstract

Let q be a prime power such that q≡ 1\pmod4. The Paley graph of order q is the graph with vertex set as the finite field \mathbbF_q and edges defined as, ab is an edge if and only if a-b is a non-zero square in \mathbbF_q. We attempt to construct a similar graph of order n, where n∈ℕ. For suitable n, we construct the graph where the vertex set is the finite commutative ring ℤ_n and edges defined as, ab is an edge if and only if a-b≡ x²\pmodn for some unit x of ℤ_n. We look at some properties of this graph. For primes p≡ 1\pmod4, Evans, Pulham and Sheehan computed the number of complete subgraphs of order 4 in the Paley graph. Very recently, Dawsey and McCarthy find the number of complete subgraphs of order 4 in the generalized Paley graph of order q. In this article, for primes p≡ 1\pmod4 and any positive integer α, we find the number of complete subgraphs of order 3 and 4 in our graph defined over ℤ_p^α.

Related

• Cliques of orders three and four in the Paley-type graphs
• Paley Graphs and Their Generalizations
• Designs from Paley graphs and Peisert graphs
• A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
• Number of complete subgraphs of Peisert graphs and finite field hypergeometric functions