Paley Graphs and Their Generalization

To construct a Paley graph, we fix a finite field and consider its elements as vertices of the Paley graph. Two vertices are connected by an edge if their difference is a square in the field. We study some important properties of the Paley graphs. In particular, we show that the Paley graphs are connected, self-complementary, and symmetric. Also we show that the Paley graph of order q is (q-1)/2 regular, and every two adjacent vertices have (q-5)/4 common neighbors, and every two non-adjacent vertices have q-1/4 common neighbors. In other words, the Paley graphs are strongly regular with parameters(q,q-1/2,q-5/4, q-1/4). Paley graphs are generalized by many mathematicians. We give three examples of these generalizations and some of their basic properties. We also define a new generalization of the Paley graphs, in which pairs of elements of a finite field are connected by an edge iff there difference belongs to the m-th power of the multiplicative group of the field, for any odd integer m 1, and we call them the m-Paley graphs. We show that the m-Paley graph of order q is complete iff gcd(m, q - 1)=1 and when d = gcd(m, q - 1) 1, the m-Paley graph is (q-1)/d regular.

Autorentext

I am an egyptian mathematician. I had my Bachelor from Al-Azhar University, Cairo-Egypt. I got a scholarship from the egyptian government to obtain my PhD from Germany. I wrote my Master Thesis as a part of a fast track Phd program in the University of Dusseldorf, Germany. In 2012 I got my Phd. under supervision of Prof. Oleg Bogopolski.