Cube graph: Difference between revisions

Latest revision as of 17:05, 29 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

The term cube graph, sometimes cube or graph of a cube, can be defined in the following equivalent ways:

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 $n$ -dimensional hypercube graph where $n=3$ .
It is the prism of cycle graph:C4, or equivalently, it is the dihedral graph on 8 vertices.

Terminological confusion

This is not to be confused with cubic graph, a term used for a 3-regular graph. Note that the cube graph is cubic, but is not the only cubic graph.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	8	As $n$ -dimensional hypercube, $n=3$ : $2^{n}=2^{3}=8$
size of edge set	12	As $n$ -dimensional hypercube, $n=3$ : $n\cdot 2^{n-1}=3\cdot 2^{3-1}=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:

Function	Value	Explanation
degree of a vertex	3	As $n$ -dimensional hypercube, $n=3$ : $n=3$
eccentricity of a vertex	3	As $n$ -dimensional hypercube, $n=3$ : $n=3$

Other numerical invariants

Function	Value	Explanation
clique number	2	As $n$ -dimensional hypercube, $n=3$ : 2 (independent of $n$ )
independence number	4	As $n$ -dimensional hypercube, $n=3$ : $2^{n-1}=2^{3-1}=4$
chromatic number	2	As $n$ -dimensional hypercube, $n=3$ : 2 (independent of $n$
radius of a graph	3	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
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
even girth	4	As $n$ -dimensional hypercube, $n=3$ : 4 (independent of $n$ for $n\geq 2$ )
girth of a graph	4	As $n$ -dimensional hypercube, $n=3$ : 4 (independent of $n$ for $n\geq 2$ )

Graph properties

Property	Satisfied?	Explanation
connected graph	Yes
regular graph	Yes	all vertices have degree three
vertex-transitive graph	Yes
cubic graph	Yes	all vertices have degree three
edge-transitive graph	Yes
symmetric graph	Yes
distance-transitive graph	Yes
bridgeless graph	Yes
strongly regular graph	No
bipartite graph	Yes

@@ Line 3: / Line 3: @@
 ==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:
+# 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==
@@ Line 17: / Line 20: @@
 ! Function !! Value !! Explanation
 |-
-| {{arithmetic function value|size of vertex set|8}} ||
+| {{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}} ||
+| {{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>
 |}
@@ Line 29: / Line 32: @@
 ! 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 42: @@
 ! 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.
@@ Line 51: / Line 54: @@
 | [[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>)
 |}
@@ Line 78: / Line 81: @@
 |-
 | [[dissatisfies property::strongly regular graph]] || No ||
+|-
+| [[satisfies property::bipartite graph]] || Yes ||
 |}