Paley, Cubic Paley, Quadruple Paley, and Generalized Paley Graphs with an Edge-Graceful Labeling

Abstract

The Paley graph Pq is a simple connected strongly regular graph with (q, q−1/2 , q−5/4 , q−1/4 ) as its parameters, where V (Pq) is the finite field Fq of order q = pn, p is an odd prime, n ∈ N, and q ≡ 1 (mod 4). In Paley graphs, two vertices are adjacent if their difference is a quadratic residue (mod q). The vertices of the  generalized Paley graph m − Pq where, m ≥ 3 is an odd integer, is V (m − Pq) = Fq and the set of edges is E(m − Pq) ={(x, y) ⇔ x − y ∈ (F∗q )m}. In 1985, edge-graceful labeling was first introduced by Lo. A graph G with order n and size m is called an edge-graceful graph if there is an injective and surjective mapping f : E(G) −→ {1, 2, 3, . . . ,m} such that the weights map fw : V (G) −→ {0, 1, 2, . . . , n − 1}  is one-to-one and onto. In this paper, we prove that Paley graphs and the generalized Paley graphs of prime order are edge-graceful, edge-even graceful, and edge-odd graceful graphs.