Cycle graph:C5: Difference between revisions

Revision as of 04:05, 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$

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

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 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.
+==Arithmetic functions==
+===Size measures===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| size of vertex set || 5 || By either definition
+|-
+| 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>
+|}
+===Other numerical invariants===
+{| class="sortable" border="1"
+! Function !! Value !! Explanation
+|-
+| {{arithmetic function value|clique number|2}} || As cycle graph <math>C_n, n = 5</math>: 2 (since <matH>n \ge 4</math>)
+|-
+| {{arithmetic function value|independence number|2}} || As cycle graph <math>C_n, n = 5</math>: Greatest integer of <math>n/2</math>, which is greatest integer of <math>5/2</matH>, which is 2
+|-
+| {{arithmetic function value|chromatic number|3}} || As cycle graph <math>C_n, n = 5</math>: 3 since <matH>n</math> is odd
+|}
 ==Graph properties==