Triangle graph - Revision history

Vipul: /* Algebraic theory */

2012-05-29T19:40:30Z

Algebraic theory

← Older revision		Revision as of 19:40, 29 May 2012
Line 81:		Line 81:
	! Algebraic invariant !! Value !! Explanation		! Algebraic invariant !! Value !! Explanation
	\|-		\|-
	\| [[characteristic polynomial of a graph\|characteristic polynomial]] \|\| <math>t^3 - 3t - 2</math> \|\|		\| [[characteristic polynomial of a graph\|characteristic polynomial]] \|\| <math>t^3 - 3t - 2</math> \|\| As <math>K_n, n = 3</math>: <math>(t + 1)^{n-1}(t - n + 1) = (t + 1)^2(t - 2) = t^3 - 3t - 2</math>
	\|-		\|-
	\| [[minimal polynomial of a graph\|minimal polynomial]] \|\| <math>t^2 - t - 2</math> \|\|		\| [[minimal polynomial of a graph\|minimal polynomial]] \|\| <math>t^2 - t - 2</math> \|\| As <math>K_n, n = 3</math>: <math>(t + 1)(t - n + 1) = t^2 - (n - 2)t - (n - 1) = t^2 - t - 2</math>
	\|-		\|-
	\| rank of adjacency matrix \|\| 3 \|\|		\| rank of adjacency matrix \|\| 3 \|\| As <math>K_n, n = 3</math>: <math>n = 3</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| -1 (multiplicity 2), 2 (multiplicity 1) \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| -1 (multiplicity 2), 2 (multiplicity 1) \|\| As <math>K_n, n = 3</math>: -1 (multiplicity <math>n - 1 = 2</math>), <math>n - 1 = 2</math> (multiplicity 1)
	\|}		\|}

Vipul at 19:37, 29 May 2012

2012-05-29T19:37:22Z

@@ Line 9: / Line 9: @@
 # It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.
 # It is the [[odd graph]] <math>O_2</math>, i.e., the [[Kneser graph]] <math>KG_{3,1}</math>.
 ==Arithmetic functions==
@@ Line 54: / Line 68: @@
 |-
 | {{arithmetic function value|girth of a graph|3}} || minimum of even and odd girth
 |}

Vipul at 03:45, 29 May 2012

2012-05-29T03:45:24Z

← Older revision		Revision as of 03:45, 29 May 2012
Line 9:		Line 9:
	# It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.		# It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.
	# It is the [[odd graph]] <math>O_2</math>, i.e., the [[Kneser graph]] <math>KG_{3,1}</math>.		# It is the [[odd graph]] <math>O_2</math>, i.e., the [[Kneser graph]] <math>KG_{3,1}</math>.

			==Arithmetic functions==

			===Size measures===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| {{arithmetic function value\|size of vertex set\|3}} \|\| As <math>C_n, n =3 </math>: <matH>n = 3</math><br>As <math>K_n , n = 3</math>: <math>n= 3</math><br>As <math>O_n, n= 2</math>: <math>\binom{2n - 1}{n - 1} = \binom{3}{1} = 3</math>
			\|-
			\| {{arithmetic function value\|size of edge set\|3}} \|\| As <math>C_n, n =3 </math>: <matH>n = 3</math><br>As <math>K_n , n = 3</math>: <math>\binom{n}{2}= \binom{3}{2} = 3</math><br>As <math>O_n, n= 2</math>: <math>\binom{2n - 1}{n - 1,n-1,1} = \binom{3}{1,1,1} = 3</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 = 3</math>: 2 (independent of <math>n</math>)<br>As <math>K_n, n = 3</math>: <math>n - 1 = 2</math><br>As <math>O_n, n = 2</math>: <math>n = 2</math>
			\|-
			\| {{arithmetic function value\|eccentricity of a vertex\|1}} \|\| As <math>C_n, n = 3</math>: greatest integer function of <math>n/2</math> equals greatest integer function of 3/2 equals 1<br>As <math>K_n, n = 3</math>: 1 (true for any <math>n \ge 2</math>)<br>As <math>O_n, n= 2</math>: <math>n - 1 = 1</math>
			\|}

			===Other numerical invariants===

			{\| class="sortable" border="1"
			! Function !! Value !! Explanation
			\|-
			\| {{arithmetic function value\|clique number\|3}} \|\| As <math>C_n, n = 3</math>: 3 (since <math>n = 3</math>; it's 2 for larger <math>n</math>)<br>As <math>K_n, n = 3</math>: <math>n= 3</math><br>As <math>O_n, n = 2</math>: 3
			\|-
			\| {{arithmetic function value\|independence number\|1}} \|\| As <math>C_n, n = 3</math>: greatest integer function of <math>n/2</math> equals greatest integer function of 3/2 equals 1<br>As <math>K_n, n = 3</math>: 1 (independent of <matH>n</math>)
			\|-
			\| {{arithmetic function value\|chromatic number\|3}} \|\| As <math>C_n, n = 3</math>: 3 since <matH>n</math> is odd<br>As <math>K_n, n= 3</math>: <math>n = 3</math>
			\|-
			\| {{arithmetic function value\|radius of a graph\|1}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
			\|-
			\| {{arithmetic function value\|diameter of a graph\|1}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
			\|-
			\| {{arithmetic function value\|odd girth\|3}} \|\| As <math>C_n, n = 3</math>: <matH>n = 3</math><br>As <math>K_n, n = 3</math>: 3 (true for any <math>n \ge 3</math>)<br>As <math>O_n, n = 2</math>: <math>2n - 1 = 2(2) - 1 = 3</math>
			\|-
			\| [[even girth]] \|\| infinite \|\| there are no cycles of even length
			\|-
			\| {{arithmetic function value\|girth of a graph\|3}} \|\| minimum of even and odd girth
			\|}

Vipul: /* Definition */

2012-05-29T03:35:12Z

Definition

← Older revision		Revision as of 03:35, 29 May 2012
Line 8:		Line 8:
	# It is the [[cycle graph]] on 3 vertices, and is denoted <math>C_3</math>.		# It is the [[cycle graph]] on 3 vertices, and is denoted <math>C_3</math>.
	# It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.		# It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.
			# It is the [[odd graph]] <math>O_2</math>, i.e., the [[Kneser graph]] <math>KG_{3,1}</math>.

Vipul at 03:48, 28 May 2012

2012-05-28T03:48:32Z

← Older revision		Revision as of 03:48, 28 May 2012
Line 1:		Line 1:
	{{particular graph}}		{{particular undirected graph}}

	==Definition==		==Definition==

Vipul: Created page with "{{particular graph}} ==Definition== This is a particular finite undirected graph defined as follows: # It is a graph whose geometric realization is a triangle: it has t..."

2012-05-28T03:48:18Z

Created page with "{{particular graph}} ==Definition== This is a particular finite undirected graph defined as follows: # It is a graph whose geometric realization is a triangle: it has t..."

New page

{{particular graph}}

==Definition==

This is a particular finite [[undirected graph]] defined as follows:

# It is a graph whose geometric realization is a triangle: it has three vertices and an edge between each pair of vertices.
# It is the [[cycle graph]] on 3 vertices, and is denoted <math>C_3</math>.
# It is the [[complete graph]] on 3 vertices, and is denoted <math>K_3</math>.