Paley graph:P17 - Revision history

Vipul: /* Definition */

2012-05-29T21:58:03Z

Definition

← Older revision		Revision as of 21:58, 29 May 2012
Line 3:		Line 3:
	==Definition==		==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==		==Arithmetic functions==

Vipul: /* Graph properties */

2012-05-29T04:46:48Z

Graph properties

← Older revision		Revision as of 04:46, 29 May 2012
Line 56:		Line 56:
	\| [[satisfies property::self-complementary graph]] \|\| Yes \|\| [[Paley graphs are self-complementary]]		\| [[satisfies property::self-complementary graph]] \|\| Yes \|\| [[Paley graphs are self-complementary]]
	\|-		\|-
	\| [[satisfies property::strongly regular graph]] \|\| Yes \|\| [[Paley graphs are strongly regular]]		\| [[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::regular graph]] \|\| Yes \|\| Follows from being strongly regular. The degree of each vertex is <math>(q - 1)/2 = (17 - 1)/2 = 8</math>.

Vipul at 18:43, 28 May 2012

2012-05-28T18:43:55Z

← Older revision		Revision as of 18:43, 28 May 2012
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]].		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==		==Graph properties==

Vipul at 04:01, 28 May 2012

2012-05-28T04:01:03Z

← Older revision		Revision as of 04:01, 28 May 2012
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]].		This graph is defined as the [[Paley graph]] <math>P_{17}</math> corresponding to [[field:F17\|the field of 17 elements]].

			==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 \|\| [[Paley graphs are strongly regular]]
			\|-
			\| [[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 \|\|
			\|}

Vipul: Created page with "{{particular undirected graph}} ==Definition== This graph is defined as the Paley graph $P_{17}$ corresponding to the field of 17 elements."

2012-05-28T03:53:42Z

Created page with "{{particular undirected graph}} ==Definition== This graph is defined as the Paley graph <math>P_{17}</math> corresponding to the field of 17 elements."

New page