Cycle graph:C5: Difference between revisions

Latest revision as of 20:05, 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 undirected graph is defined in the following equivalent ways:

It is the cycle graph on 5 vertices, i.e., the graph $C_{5}$
It is the Paley graph $P_{5}$ corresponding to the field of 5 elements
It is the unique (up to graph isomorphism) self-complementary graph on a set of 5 vertices

Note that 5 is the only size for which the Paley graph coincides with the cycle graph. In general, the Paley graph $P_{q}$ can be expressed as an edge-disjoint union of $(q-1)/4$ cycle graphs. In our case, $(5-1)/4=1$ , so the graphs coincide.

Explicit descriptions

Descriptions of vertex set and edge set

Vertex set: $\{1,2,3,4,5\}$

Edge set: $\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{1,5\}\}$

Adjacency matrix

The adjacency matrix with the above choice of vertex set is:

${\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\\\end{pmatrix}}$

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	5	By either definition
size of edge set	5	As $C_{n},n=5$ : $n=5$ As $P_{q},q=5$ : $q(q-1)/4=5(4)/4=5$

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	2	As $C_{n},n=5(n\geq 3)$ : 2 As $P_{q},q=5$ : $(q-1)/2=(5-1)/2=2$
eccentricity of a vertex	2	As $C_{n},n=5(n\geq 3)$ : greatest integer of $n/2$ equals 2 As $P_{q},q=5$ : 2 (follows from every element of a finite field is expressible as a sum of two squares)

Other numerical invariants

Function	Value	Explanation
clique number	2	As cycle graph $C_{n},n=5$ : 2 (since $n\geq 4$ )
independence number	2	As cycle graph $C_{n},n=5$ : Greatest integer of $n/2$ , which is greatest integer of $5/2$ , which is 2
chromatic number	3	As cycle graph $C_{n},n=5$ : 3 since $n$ is odd
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	5	As $C_{n},n=5$ : $n=5$ As $P_{q},q=5$ : 5. Note that for all higher $q$ , 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	1	As $C_{n},n=5$ : 1 (doesn't depend on $n$ ) As $P_{q},q=5$ : $q(q-5)/4+1=5(5-5)/4+1=1$

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. Also follows from the fact that cycle graphs are 2-regular.
conference graph	Yes	Paley graphs are conference graphs
symmetric graph	Yes
edge-transitive graph	Yes	Follows on account of being Paley and also on account of being cyclic
vertex-transitive graph	Yes

Graph operations

Operation	Graph obtained as a result of the operation
complement of a graph	isomorphic to the cycle graph, because the graph is self-complementary
line graph	complement of Petersen graph
prism of a graph	dihedral graph on 10 vertices

Algebraic theory

The adjacency matrix, well defined up to conjugation by permutations, is:

${\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\\\end{pmatrix}}$

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^{5}-5t^{3}+5t-2=(t^{2}+t-1)^{2}(t-2)$
minimal polynomial	$t^{3}-t^{2}-3t+2=(t^{2}+t-1)(t-2)$
rank of adjacency matrix	3
eigenvalues (roots of characteristic polynomial)	2 (1 time), ${\frac {-1+{\sqrt {5}}}{2}}$ (2 times), ${\frac {-1-{\sqrt {5}}}{2}}$ (2 times)

Realization

As Cayley graph

Note that for this to be the Cayley graph of a group, the group must have order 5, and the generating set with respect to which we construct the Cayley graph must be a symmetric subset of the group of size equal to the degrees of vertices in the graph, which is 2.

Group	Choice of symmetric set that is a generating set for which the Cayley graph is this
cyclic group:Z5	cyclic generator and its inverse

@@ Line 10: / Line 10: @@
 Note that 5 is the only size for which the Paley graph coincides with the cycle graph. In general, the Paley graph <math>P_q</math> can be expressed as an edge-disjoint union of <math>(q - 1)/4</math> [[cycle graph]]s. In our case, <math>(5 - 1)/4 = 1</math>, so the graphs coincide.
+==Explicit descriptions==
+===Descriptions of vertex set and edge set===
+Vertex set: <math>\{ 1,2,3,4,5 \}</math>
+Edge set: <math>\{ \{ 1,2 \}, \{ 2,3 \}, \{ 3,4 \} , \{ 4, 5 \}, \{ 1, 5 \} \}</math>
+===Adjacency matrix===
+The adjacency matrix with the above choice of vertex set is:
+<math>\begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\\end{pmatrix}</math>
 ==Arithmetic functions==
@@ Line 21: / Line 35: @@
 |-
 | {{arithmetic function value|size of edge set|5}} || As <matH>C_n, n = 5</math>: <math>n = 5</math><br>As <math>P_q, q = 5</math>: <math>q(q - 1)/4 = 5(4)/4 = 5</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|2}} || As <math>C_n, n = 5 (n \ge 3)</math>: 2<br>As <math>P_q, q = 5</math>: <math>(q -1)/2 = (5 - 1)/2 = 2</math>
+|-
+| {{arithmetic function value|eccentricity of a vertex|2}} || As <matH>C_n, n = 5 (n \ge 3)</math>: greatest integer of <matH>n/2</math> equals 2<br>As <math>P_q, q = 5</math>: 2 (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]])
 |}
@@ Line 33: / Line 59: @@
 |-
 | {{arithmetic function value|chromatic number|3}} || As cycle graph <math>C_n, n = 5</math>: 3 since <matH>n</math> is odd
+|-
+| {{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|5}} || As <math>C_n, n = 5</math>: <matH>n = 5</math><br>As <math>P_q, q = 5</matH>: 5. Note that for ''all'' higher <math>q</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|1}} || As <math>C_n, n = 5</math>: 1 (doesn't depend on <matH>n</math>)<br>As <math>P_q, q = 5</math>: <math>q(q - 5)/4 + 1 = 5(5 - 5)/4 + 1 = 1</math>
 |}
@@ Line 53: / Line 87: @@
 |-
 | [[satisfies property::vertex-transitive graph]] || Yes ||
+|}
+==Graph operations==
+{| class="sortable" border="1"
+! Operation !! Graph obtained as a result of the operation
+|-
+| [[complement of a graph]] || isomorphic to the cycle graph, because the graph is self-complementary
+|-
+| [[line graph]] || [[complement of Petersen graph]]
+|-
+| [[prism of a graph]] || [[dihedral graph on 10 vertices]]
+|}
+==Algebraic theory==
+The adjacency matrix, well defined up to conjugation by permutations, is:
+<math>\begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\\end{pmatrix}</math>
+{| class="sortable" border="1"
+! Algebraic invariant !! Value !! Explanation
+|-
+| [[characteristic polynomial of a graph|characteristic polynomial]] || <math>t^5 - 5t^3 + 5t - 2 = (t^2 + t - 1)^2(t - 2)</math> ||
+|-
+| [[minimal polynomial of a graph|minimal polynomial]] || <math>t^3 - t^2 - 3t + 2 = (t^2 + t - 1)(t - 2)</math>
+|-
+| rank of adjacency matrix || 3 ||
+|-
+| eigenvalues (roots of characteristic polynomial) || 2 (1 time), <math>\frac{-1 + \sqrt{5}}{2}</math> (2 times), <math>\frac{-1 - \sqrt{5}}{2}</math> (2 times) ||
+|}
+==Realization==
+===As Cayley graph===
+Note that for this to be the Cayley graph of a group, the group must have order 5, and the generating set with respect to which we construct the Cayley graph must be a [[symmetric subset]] of the group of size equal to the degrees of vertices in the graph, which is 2.
+{| class="sortable" border="1"
+! Group !! Choice of [[groupprops:symmetric subset|symmetric set]] that is a [[groupprops:generating set|generating set]] for which the Cayley graph is this
+|-
+| [[groupprops:cyclic group:Z5|cyclic group:Z5]] || cyclic generator and its inverse
 |}