Petersen graph - Revision history

Vipul at 21:21, 23 December 2012

2012-12-23T21:21:31Z

← Older revision		Revision as of 21:21, 23 December 2012
Line 1:		Line 1:
	{{particular undirected graph}}		{{particular undirected graph}}
	[[File:Petersen graph.svg\|thumb\|300px\|right}\|the Petersen graph is typically drawn as a pentagon with a pentagram inside.]]		[[File:Petersen graph.svg\|thumb\|300px\|right\|the Petersen graph is typically drawn as a pentagon with a pentagram inside.]]
			[[File:Kneser graph KG(5,2).svg\|thumb\|300px\|right\|the Petersen graph as KG(5,2). The subsets corresponding to each vertex are indicated in the bubble for that vertex.]]
	==Definition==		==Definition==

Vipul at 21:13, 23 December 2012

2012-12-23T21:13:54Z

← Older revision		Revision as of 21:13, 23 December 2012
Line 1:		Line 1:
	{{particular undirected graph}}		{{particular undirected graph}}
	[[File:Petersen graph.svg\|thumb\|~~400px~~\|right]]		[[File:Petersen graph.svg\|thumb\|300px\|right}\|the Petersen graph is typically drawn as a pentagon with a pentagram inside.]]
	==Definition==		==Definition==

Vipul at 21:13, 23 December 2012

2012-12-23T21:13:29Z

← Older revision		Revision as of 21:13, 23 December 2012
Line 1:		Line 1:
	{{particular undirected graph}}		{{particular undirected graph}}
			[[File:Petersen graph.svg\|thumb\|400px\|right]]
	==Definition==		==Definition==

Vipul at 04:09, 29 May 2012

2012-05-29T04:09:49Z

← Older revision		Revision as of 04:09, 29 May 2012
Line 7:		Line 7:
	# It is the [[defining ingredient::complement of a graph\|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].		# It is the [[defining ingredient::complement of a graph\|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].
	# It is the [[defining ingredient::odd graph]] with parameter 3, i.e., the graph <math>O_3</math>. Explicitly, this is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.		# It is the [[defining ingredient::odd graph]] with parameter 3, i.e., the graph <math>O_3</math>. Explicitly, this is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
	# It is the unique 5-[[defining ingredient::cage]].		# It is the unique (3,5)-[[defining ingredient::cage]].

	==Arithmetic functions==		==Arithmetic functions==

Vipul: /* Arithmetic functions */

2012-05-29T04:01:01Z

Arithmetic functions

← Older revision		Revision as of 04:01, 29 May 2012
Line 50:		Line 50:
	\| {{arithmetic function value\|odd girth\|5}} \|\| As <math>O_n ,n = 3</math>: <math>2n - 1 = 2(3) - 1 = 5</math>		\| {{arithmetic function value\|odd girth\|5}} \|\| As <math>O_n ,n = 3</math>: <math>2n - 1 = 2(3) - 1 = 5</math>
	\|-		\|-
	\| {{arithmetic function value\|even girth\|6}} \|\| As <math>_n, n = 3</math>: 6 (we use that <matH>n \ge 3</math>)		\| {{arithmetic function value\|even girth\|6}} \|\| As <math>O_n, n = 3</math>: 6 (we use that <matH>n \ge 3</math>)
	\|-		\|-
	\| {{arithmetic function value\|girth of a graph\|5}} \|\| As <matH>O_n, n = 3</math>: <math>\min \{ 2n - 1,6 \}</math>		\| {{arithmetic function value\|girth of a graph\|5}} \|\| As <matH>O_n, n = 3</math>: <math>\min \{ 2n - 1,6 \}</math>

Vipul: /* Graph properties */

2012-05-29T03:28:34Z

Graph properties

← Older revision		Revision as of 03:28, 29 May 2012
Line 64:		Line 64:
	\| [[satisfies property::regular graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are regular		\| [[satisfies property::regular graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are regular
	\|-		\|-
	\| [[satisfies property::vertex-~~tranitive~~ graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are vertex-transitive		\| [[satisfies property::vertex-transitive graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are vertex-transitive
	\|-		\|-
	\| [[satisfies property::strongly regular graph]] \|\| Yes \|\| This follows on account of it being a Kneser graph of the form <math>KG_{m,2}</math>, i.e., the key is that the subset sizes are 2		\| [[satisfies property::strongly regular graph]] \|\| Yes \|\| This follows on account of it being a Kneser graph of the form <math>KG_{m,2}</math>, i.e., the key is that the subset sizes are 2

Vipul: /* Graph properties */

2012-05-29T03:28:19Z

Graph properties

← Older revision		Revision as of 03:28, 29 May 2012
Line 83:		Line 83:
	\|-		\|-
	\| [[satisfies property::snark]] \|\| Yes \|\|		\| [[satisfies property::snark]] \|\| Yes \|\|
	\|]		\|}

Vipul at 03:28, 29 May 2012

2012-05-29T03:28:00Z

← Older revision		Revision as of 03:28, 29 May 2012
Line 54:		Line 54:
	\| {{arithmetic function value\|girth of a graph\|5}} \|\| As <matH>O_n, n = 3</math>: <math>\min \{ 2n - 1,6 \}</math>		\| {{arithmetic function value\|girth of a graph\|5}} \|\| As <matH>O_n, n = 3</math>: <math>\min \{ 2n - 1,6 \}</math>
	\|}		\|}

			==Graph properties==

			{\| class="sortable" border="1"
			! Property !! Satisfied? !! Explanation
			\|-
			\| [[satisfies property::connected graph]] \|\| Yes \|\| all odd graphs are connected. More generally, all Kneser graphs <math>KG_{m,k}</math> are connected for <math>k < m/2</math>.
			\|-
			\| [[satisfies property::regular graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are regular
			\|-
			\| [[satisfies property::vertex-tranitive graph]] \|\| Yes \|\| all odd graphs, and more generally all [[Kneser graph]]s, are vertex-transitive
			\|-
			\| [[satisfies property::strongly regular graph]] \|\| Yes \|\| This follows on account of it being a Kneser graph of the form <math>KG_{m,2}</math>, i.e., the key is that the subset sizes are 2
			\|-
			\| [[satisfies property::edge-transitive graph]] \|\| Yes \|\|
			\|-
			\| [[satisfies property::symmetric graph]] \|\| Yes \|\|
			\|-
			\| [[satisfies property::distance-transitive graph]] \|\| Yes \|\|
			\|-
			\| [[dissatisfies property::self-complementary graph]] \|\| No \|\| The degree is 3 and the number of vertices is 10. For the graph to be self-complementary, a necessary condition is that the number of vertices should be 1 + twice the degree
			\|-
			\| [[satisfies property::cubic graph]] \|\| Yes \|\| The degree of every vertex is 3, as computed above.
			\|-
			\| [[satisfies property::bridgeless graph]] \|\| Yes \|\|
			\|-
			\| [[satisfies property::cage]] \|\| Yes \|\|
			\|-
			\| [[satisfies property::snark]] \|\| Yes \|\|
			\|]

Vipul at 03:16, 29 May 2012

2012-05-29T03:16:38Z

@@ Line 6: / Line 6: @@
 # It is the [[defining ingredient::complement of a graph|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].
-# It is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
+# It is the [[defining ingredient::odd graph]] with parameter 3, i.e., the graph <math>O_3</math>. Explicitly, this is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
 # It is the unique 5-[[defining ingredient::cage]].

Vipul at 18:11, 28 May 2012

2012-05-28T18:11:14Z

← Older revision		Revision as of 18:11, 28 May 2012
Line 7:		Line 7:
	# It is the [[defining ingredient::complement of a graph\|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].		# It is the [[defining ingredient::complement of a graph\|complement]] of the [[defining ingredient::line graph]] of [[defining ingredient::complete graph:K5]].
	# It is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.		# It is the [[defining ingredient::Kneser graph]] <math>KG_{5,2}</math>: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
			# It is the unique 5-[[defining ingredient::cage]].