Paley graph:P17

This article defines a particular undirected graph, i.e., the definition here determines the graph uniquely up to graph isomorphism.
View a complete list of particular undirected graphs

Definition

This graph is defined as the Paley graph $P_{17}$ corresponding to the field of 17 elements. It is also denoted $QR(17)$.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	17	As $P_{q},q=17$: $q=17$
size of edge set	68	As $P_{q},q=17$: $q(q-1)/4=(17)(16)/4=68$

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	8	As $P_{q},q=17$: $(q-1)/2=(17-1)/2=8$
eccentricity of a vertex	2	As $P_{q},q=17$: 2 (independent of $q$) Follows from every element of a finite field is expressible as a sum of two squares

Other numerical invariants

Function	Value	Explanation
clique number	3	Based on the explanation for the girth, the clique number must be at least three. Showing that there is no 4-clique requires some case checking.
independence number	3	Same as clique number. The two numbers are equal because the Paley graph is a self-complementary graph and independence number equals clique number of complement
chromatic number	Fill this in later	Fill this in later
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
girth of a graph	3	As $P_{q},q=17,q>5$: the girth of the graph is 3, due to the fact that there are $(q-5)/4$ pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever $q>5$.
circuit rank	52	As $P_{q},q=17$: The circuit rank is $(q-1)(q-4)/4$, which becomes $(16)(13)/4=52$

Graph properties

Property	Satisfied?	Explanation
self-complementary graph	Yes	Paley graphs are self-complementary
strongly regular graph	Yes	strongly regular with parameters $(17,8,3,4)$. Follows from the fact that Paley graphs are strongly regular. The parameters in general are $(q,(q-1)/2,(q-5)/4,(q-1)/4)$.
regular graph	Yes	Follows from being strongly regular. The degree of each vertex is $(q-1)/2=(17-1)/2=8$.
conference graph	Yes	Paley graphs are conference graphs
symmetric graph	Yes
edge-transitive graph	Yes	Follows on account of being Paley
vertex-transitive graph	Yes