Cycle graph:C5: Difference between revisions

Revision as of 17:56, 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 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.

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$ .

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

@@ Line 49: / Line 49: @@
 |-
 | {{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>.
 |}