Cycle graph:C5: Difference between revisions

Revision as of 03:59, 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.

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 8: / Line 8: @@
 # It is the [[Paley graph]] <math>P_5</math> 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 <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.
+==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. Also follows from the fact that cycle graphs are 2-regular.
+|-
+| [[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 and also on account of being cyclic
+|-
+| [[satisfies property::vertex-transitive graph]] || Yes ||
+|}