Cube graph: Difference between revisions

Revision as of 16:21, 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, 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 $n$ -dimensional hypercube graph where $n=3$ .

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$ -hypercube graph, $n=3$ : $2^{n}=2^{3}=8$
size of edge set	12	As $n$ -hypercube graph, $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

@@ 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.
+Alternatively, it can be thought of as the <math>n</math>-dimensional hypercube graph where <math>n = 3</math>.
 ==Terminological confusion==
@@ Line 17: / Line 19: @@
 ! 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
 |-
-| {{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
 |-
-| {{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 53: @@
 | [[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>)
 |}