Square graph: Difference between revisions

Revision as of 16:34, 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

This undirected graph is defined in the following equivalent ways:

It is the cycle graph on 4 vertices, denoted $C_{4}$ .
It is the complete bipartite graph $K_{2, 2}$
it is the 2-dimensional hypercube graph.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	4	As cycle graph $C_{n}, n = 4$ : $n = 4$ As complete bipartite graph $K_{m, n}, m = n = 2$ : $m + n = 2 + 2 = 4$ As $n$ -dimensional hypercube, $n = 2$ : $2^{n} = 2^{2} = 4$
size of edge set	4	As cycle graph $C_{n}, n = 4$ : $n = 4$ As complete bipartite graph $K_{m, n}, m = n = 2$ : $m n = 2 (2) = 4$ As $n$ -dimensional hypercube, $n = 2$ : $n \cdot 2^{n - 1} = 2 \cdot 2^{2 - 1} = 4$

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	2	As cycle graph $C_{n}, n = 4$ : 2 (independent of $n$ ) As complete bipartite graph $K_{m, n}, m = n = 2$ : Since $m, n$ are equal, the graph is vertex-transitive and $(m = n)$ -regular, so we get $m = n = 2$ As $n$ -dimensional hypercube, $n = 2$ : $n = 2$
eccentricity of a vertex	2	As cycle graph $C_{n}, n = 4$ : greatest integer of $n / 2$ equals greater integer of 4/2 equals 2 As complete bipartite graph $K_{m, n}, m = n = 2$ : 2 (independent of $m, n$ , though it uses that both numbers are greater than 1) As $n$ -dimensional hypercube, $n = 2$ : $n = 2$

Other numerical invariants

Function	Value	Explanation
clique number	2	As cycle graph $C_{n}, n = 4$ : 2 (independent of $n$ for $n \geq 4$ ) As $K_{m, n}, m = n = 2$ : 2 (independent of $m, n$ , follows from being bipartite) As $n$ -dimensional hypercube, $n = 2$ : 2 (independent of $n$ )
independence number	2	As cycle graph $C_{n}, n = 4$ : greatest integer of $n / 2$ equals greatest integer of 4/2 equals 2 As $K_{m, n}, m = n = 2$ : $max {m, n} = max {2, 2} = 2$ As $n$ -dimensional hypercube, $n = 2$ : $2^{n - 1} = 2^{2 - 1} = 2$
chromatic number	2	As cycle graph $C_{n}, n = 4$ : 2 (in general, it is 2 for even $n$ and 3 for odd $n$ As $K_{m, n}, m = n = 2$ : 2 (independent of $m, n$ , follows from being bipartite) As $n$ -dimensional hypercube, $n = 2$ : 2 (independent of $n$ , follows from being bipartite)
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	infinite
even girth	4	As cycle graph $C_{n}, n = 4$ : $n = 4$ (since $n$ even) As complete bipartite graph $K_{m, n}, m = n = 2$ : 4 (independent of $m, n$ as long as both are greater than 1) As $n$ -dimensional hypercube, $n = 2$ : 4 (independent of $n$ for $n \geq 2$ )
girth of a graph	4	As cycle graph $C_{n}, n = 4$ : $n = 4$ As complete bipartite graph $K_{m, n}, m = n = 2$ : 4 (independent of $m, n$ as long as both are greater than 1) As $n$ -dimensional hypercube, $n = 2$ : 4 (independent of $n$ for $n \geq 2$ )

@@ Line 40: / Line 40: @@
 | {{arithmetic function value|clique number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (independent of <math>n</math> for <math>n \ge 4</math>) <br>As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite)<br>As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>)
 |-
-| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2<br>As <math>K_{m,n}, m = n = 2<?math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math><br>As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
+| {{arithmetic function value|independence number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: greatest integer of <math>n/2</math> equals greatest integer of 4/2 equals 2<br>As <math>K_{m,n}, m = n = 2</math>: <math>\max \{ m,n \} = \max \{ 2,2 \} = 2</math><br>As <math>n</math>-dimensional hypercube, <math>n = 2</math>: <math>2^{n-1} = 2^{2-1} = 2</math>
 |-
 | {{arithmetic function value|chromatic number|2}} || As [[cycle graph]] <math>C_n, n = 4</math>: 2 (in general, it is 2 for even <math>n</math> and 3 for odd <math>n</math> <br>As <math>K_{m,n}, m = n = 2</math>: 2 (independent of <math>m,n</math>, follows from being bipartite)<br>As <math>n</math>-dimensional hypercube, <math>n = 2</math>: 2 (independent of <math>n</math>, follows from being bipartite)