Paley graph:P17: Difference between revisions

Revision as of 18:43, 28 May 2012

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.

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	Paley graphs are strongly regular
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

@@ Line 4: / Line 4: @@
 This graph is defined as the [[Paley graph]] <math>P_{17}</math> corresponding to [[field:F17|the field of 17 elements]].
+==Arithmetic functions==
+===Size measures===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|size of vertex set|17}} || As <math>P_q,q = 17</math>: <math>q = 17</math>
+|-
+| {{arithmetic function value|size of edge set|68}} || As <math>P_q, q = 17</math>: <matH>q(q - 1)/4 = (17)(16)/4 = 68</math>
+|}
+===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:
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|degree of a vertex|8}} || As <math>P_q, q = 17</math>: <matH>(q - 1)/2 = (17 - 1)/2 = 8</math>
+|-
+| {{arithmetic function value|eccentricity of a vertex|2}} || As <math>P_q, q = 17</math>: 2 (independent of <matH>q</math>)<br>Follows from [[groupprops:every element of a finite field is expressible as a sum of two squares|every element of a finite field is expressible as a sum of two squares]]
+|}
+===Other numerical invariants===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|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.
+|-
+| {{arithmetic function value|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]] || {{fillin}} || {{fillin}}
+|-
+| {{arithmetic function value|radius of a graph|2}} || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
+|-
+| {{arithmetic function value|diameter of a graph|2}} || Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
+|-
+| {{arithmetic function value|girth of a graph|3}} || As <math>P_q, q = 17, q > 5</math>: the girth of the graph is 3, due to the fact that there are <math>(q - 5)/4</math> pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever <matH>q > 5</math>.
+|-
+| {{arithmetic function value|circuit rank|52}} || As <math>P_q, q=17</math>: The circuit rank is <math>(q - 1)(q - 4)/4</math>, which becomes <math>(16)(13)/4 = 52</math>
+|}
 ==Graph properties==