Paley graph:P17: Difference between revisions

Latest revision as of 21:58, 29 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. 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

@@ Line 3: / Line 3: @@
 ==Definition==
-This graph is defined as the [[Paley graph]] <math>P_{17}</math> corresponding to [[field:F17|the field of 17 elements]].
+This graph is defined as the [[Paley graph]] <math>P_{17}</math> corresponding to [[field:F17|the field of 17 elements]]. It is also denoted <math>QR(17)</math>.
+==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==
+{| class="sortable" border="1"
+! Property !! Satisfied? !! Explanation
+|-
+| [[satisfies property::self-complementary graph]] || Yes || [[Paley graphs are self-complementary]]
+|-
+| [[satisfies property::strongly regular graph]] || Yes || strongly regular with parameters <math>(17,8,3,4)</math>. Follows from the fact that [[Paley graphs are strongly regular]]. The parameters in general are <math>(q, (q -1)/2, (q - 5)/4, (q - 1)/4)</math>.
+|-
+| [[satisfies property::regular graph]] || Yes || Follows from being strongly regular. The degree of each vertex is <math>(q - 1)/2 = (17 - 1)/2 = 8</math>.
+|-
+| [[satisfies property::conference graph]] || Yes || [[Paley graphs are conference graphs]]
+|-
+| [[satisfies property::symmetric graph]] || Yes ||
+|-
+| [[satisfies property::edge-transitive graph]] || Yes || Follows on account of being Paley
+|-
+| [[satisfies property::vertex-transitive graph]] || Yes ||
+|}