Cycle graph:C5 - Revision history

Vipul: /* Algebraic theory */

2012-05-29T20:05:10Z

Algebraic theory

@@ Line 117: / Line 117: @@
 |-
 | 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) ||
 |}

Vipul at 20:01, 29 May 2012

2012-05-29T20:01:23Z

@@ 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==
@@ Line 73: / Line 87: @@
 |-
 | [[satisfies property::vertex-transitive graph]] || Yes ||
 |}

Vipul: /* Other numerical invariants */

2012-05-28T18:21:19Z

Other numerical invariants

← Older revision		Revision as of 18:21, 28 May 2012
Line 51:		Line 51:
	\|-		\|-
	\| {{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\|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>
	\|}		\|}

Vipul: /* Other numerical invariants */

2012-05-28T17:56:57Z

Other numerical invariants

← Older revision		Revision as of 17:56, 28 May 2012
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\|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>.
	\|}		\|}

Vipul: /* Arithmetic functions */

2012-05-28T17:53:22Z

Arithmetic functions

@@ Line 21: / Line 21: @@
 |-
 | {{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>
 |}
@@ Line 33: / Line 45: @@
 |-
 | {{arithmetic function value|chromatic number|3}} || As cycle graph <math>C_n, n = 5</math>: 3 since <matH>n</math> is odd
 |}

Vipul at 04:12, 28 May 2012

2012-05-28T04:12:54Z

← Older revision		Revision as of 04:12, 28 May 2012
Line 18:		Line 18:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| size of vertex set \|\| 5 \|\| By either definition		\| {{arithmetic function value\|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>		\| {{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>
	\|}		\|}

Vipul at 04:05, 28 May 2012

2012-05-28T04:05:48Z

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

Vipul at 03:59, 28 May 2012

2012-05-28T03:59:59Z

← Older revision		Revision as of 03:59, 28 May 2012
Line 8:		Line 8:
	# It is the [[Paley graph]] <math>P_5</math> corresponding to the field of 5 elements		# 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		# 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 \|\|
			\|}

Vipul: Created page with "{{particular undirected graph}} ==Definition== This undirected graph is defined in the following equivalent ways: # It is the cycle graph on 5 vertices, i.e., the g..."

2012-05-28T03:51:12Z

Created page with "{{particular undirected graph}} ==Definition== This undirected graph is defined in the following equivalent ways: # It is the cycle graph on 5 vertices, i.e., the g..."

New page

{{particular undirected graph}}

==Definition==

This [[undirected graph]] is defined in the following equivalent ways:

# It is the [[cycle graph]] on 5 vertices, i.e., the graph <math>C_5</math>
# 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