Cube graph - Revision history

Vipul at 17:05, 29 May 2012

2012-05-29T17:05:45Z

← Older revision		Revision as of 17:05, 29 May 2012
Line 3:		Line 3:
	==Definition==		==Definition==

	The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', ~~refers to~~ the ~~cube in three-dimensional space viewed as a graph~~: ~~the vertices are the vertices of the cube, and the edges are the edges of the cube.~~		The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', can be defined in the following equivalent ways:

	Alternatively, it can be thought of as the <math>n</math>-dimensional hypercube graph where <math>n = 3</math>.		# It is the cube in three-dimensional space viewed as a graph: the vertices are the vertices of the cube, and the edges are the edges of the cube. Alternatively, it can be thought of as the <math>n</math>-dimensional [[hypercube graph]] where <math>n = 3</math>.
			# It is the [[prism of a graph\|prism]] of [[cycle graph:C4]], or equivalently, it is the [[dihedral graph]] on 8 vertices.

	==Terminological confusion==		==Terminological confusion==

Vipul: /* Graph properties */

2012-05-29T16:38:16Z

Graph properties

← Older revision		Revision as of 16:38, 29 May 2012
Line 80:		Line 80:
	\|-		\|-
	\| [[dissatisfies property::strongly regular graph]] \|\| No \|\|		\| [[dissatisfies property::strongly regular graph]] \|\| No \|\|
			\|-
			\| [[satisfies property::bipartite graph]] \|\| Yes \|\|
	\|}		\|}

Vipul: /* Arithmetic functions */

2012-05-29T16:23:08Z

Arithmetic functions

← Older revision		Revision as of 16:23, 29 May 2012
Line 19:		Line 19:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| {{arithmetic function value\|size of vertex set\|8}} \|\| As <math>n</math>-hypercube ~~graph~~, <math>n = 3</math>: <math>2^n = 2^3 = 8</math>		\| {{arithmetic function value\|size of vertex set\|8}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: <math>2^n = 2^3 = 8</math>
	\|-		\|-
	\| {{arithmetic function value\|size of edge set\|12}} \|\| As <math>n</math>-hypercube ~~graph~~, <math>n = 3</math>: <math>n \cdot 2^{n-1} = 3 \cdot 2^{3 - 1} = 12</math>		\| {{arithmetic function value\|size of edge set\|12}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: <math>n \cdot 2^{n-1} = 3 \cdot 2^{3 - 1} = 12</math>
	\|}		\|}

Vipul at 16:21, 29 May 2012

2012-05-29T16:21:51Z

Vipul at 04:05, 29 May 2012

2012-05-29T04:05:12Z

@@ Line 4: / Line 4: @@
 The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed as a graph: the vertices are the vertices of the cube, and the edges are the edges of the cube.
 ==Arithmetic functions==
@@ Line 50: / Line 54: @@
 |-
 | {{arithmetic function value|girth of a graph|4}} ||
 |}

Vipul: Created page with "{{particular undirected graph}} ==Definition== The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed..."

2012-05-29T04:01:09Z

Created page with "{{particular undirected graph}} ==Definition== The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed..."

New page

{{particular undirected graph}}

==Definition==

The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed as a graph: the vertices are the vertices of the cube, and the edges are the edges of the cube.

==Arithmetic functions==

===Size measures===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|size of vertex set|8}} ||
|-
| {{arithmetic function value|size of edge set|12}} ||
|}

===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|3}} ||
|-
| {{arithmetic function value|eccentricity of a vertex|3}} ||
|}

===Other numerical invariants===

{| class="sortable" border="1"
! Function !! Value !! Explanation
|-
| {{arithmetic function value|clique number|2}} ||
|-
| {{arithmetic function value|independence number|4}} ||
|-
| {{arithmetic function value|chromatic number|2}} ||
|-
| {{arithmetic function value|radius of a graph|3}} || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
|-
| {{arithmetic function value|diameter of a graph|3}} || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
|-
| [[odd girth]] || infinite ||
|-
| {{arithmetic function value|even girth|4}} ||
|-
| {{arithmetic function value|girth of a graph|4}} ||
|}

← Older revision		Revision as of 16:21, 29 May 2012
Line 4:		Line 4:

	The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed as a graph: the vertices are the vertices of the cube, and the edges are the edges of the cube.		The term '''cube graph''', sometimes '''cube''' or '''graph of a cube''', refers to the cube in three-dimensional space viewed as a graph: the vertices are the vertices of the cube, and the edges are the edges of the cube.

			Alternatively, it can be thought of as the <math>n</math>-dimensional hypercube graph where <math>n = 3</math>.

	==Terminological confusion==		==Terminological confusion==
Line 17:		Line 19:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| {{arithmetic function value\|size of vertex set\|8}} \|\|		\| {{arithmetic function value\|size of vertex set\|8}} \|\| As <math>n</math>-hypercube graph, <math>n = 3</math>: <math>2^n = 2^3 = 8</math>
	\|-		\|-
	\| {{arithmetic function value\|size of edge set\|12}} \|\|		\| {{arithmetic function value\|size of edge set\|12}} \|\| As <math>n</math>-hypercube graph, <math>n = 3</math>: <math>n \cdot 2^{n-1} = 3 \cdot 2^{3 - 1} = 12</math>
	\|}		\|}

Line 29:		Line 31:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| {{arithmetic function value\|degree of a vertex\|3}} \|\|		\| {{arithmetic function value\|degree of a vertex\|3}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: <math>n = 3</math>
	\|-		\|-
	\| {{arithmetic function value\|eccentricity of a vertex\|3}} \|\|		\| {{arithmetic function value\|eccentricity of a vertex\|3}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: <math>n = 3</math>
	\|}		\|}

Line 39:		Line 41:
	! Function !! Value !! Explanation		! Function !! Value !! Explanation
	\|-		\|-
	\| {{arithmetic function value\|clique number\|2}} \|\|		\| {{arithmetic function value\|clique number\|2}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: 2 (independent of <math>n</math>)
	\|-		\|-
	\| {{arithmetic function value\|independence number\|4}} \|\|		\| {{arithmetic function value\|independence number\|4}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: <math>2^{n-1} = 2^{3-1} = 4</math>
	\|-		\|-
	\| {{arithmetic function value\|chromatic number\|2}} \|\|		\| {{arithmetic function value\|chromatic number\|2}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: 2 (independent of <math>n</math>
	\|-		\|-
	\| {{arithmetic function value\|radius of a graph\|3}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.		\| {{arithmetic function value\|radius of a graph\|3}} \|\| Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
Line 51:		Line 53:
	\| [[odd girth]] \|\| infinite \|\|		\| [[odd girth]] \|\| infinite \|\|
	\|-		\|-
	\| {{arithmetic function value\|even girth\|4}} \|\|		\| {{arithmetic function value\|even girth\|4}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
	\|-		\|-
	\| {{arithmetic function value\|girth of a graph\|4}} \|\|		\| {{arithmetic function value\|girth of a graph\|4}} \|\| As <math>n</math>-dimensional hypercube, <math>n = 3</math>: 4 (independent of <math>n</math> for <math>n \ge 2</math>)
	\|}		\|}