Square graph

From Graph
Jump to: navigation, search
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, called the square graph, is defined in the following equivalent ways:

  1. It is the cycle graph on 4 vertices, denoted .
  2. It is the complete bipartite graph
  3. It is the 2-dimensional hypercube graph.
  4. It is the 2-dimensional hyperoctahedron graph.

Explicit descriptions

Description of vertex set and edge set

Vertex set:

Edge set:

Note that with this description, the two parts in a bipartite graph description are and .

Adjacency matrix

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

Arithmetic functions

Size measures

Function Value Explanation
size of vertex set 4 As cycle graph :
As complete bipartite graph :
As -dimensional hypercube, :
size of edge set 4 As cycle graph :
As complete bipartite graph :
As -dimensional hypercube, :

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

Other numerical invariants

Function Value Explanation
clique number 2 As cycle graph : 2 (independent of for )
As : 2 (independent of , follows from being bipartite)
As -dimensional hypercube, : 2 (independent of )
independence number 2 As cycle graph : greatest integer of equals greatest integer of 4/2 equals 2
As :
As -dimensional hypercube, :
chromatic number 2 As cycle graph : 2 (in general, it is 2 for even and 3 for odd
As : 2 (independent of , follows from being bipartite)
As -dimensional hypercube, : 2 (independent of , 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 As cycle graph : infinite (since even)
As : infinite, since bipartite
As -dimensional hypercube, : infinite, since bipartite
even girth 4 As cycle graph : (since even)
As complete bipartite graph : 4 (independent of as long as both are greater than 1)
As -dimensional hypercube, : 4 (independent of for )
girth of a graph 4 As cycle graph :
As complete bipartite graph : 4 (independent of as long as both are greater than 1)
As -dimensional hypercube, : 4 (independent of for )

Graph properties

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

Graph operations

Operation Graph obtained as a result of the operation
complement of a graph matching graph on 4 vertices
line graph isomorphic to the original graph
prism of a graph cube graph

Algebraic theory

Adjacency matrix

The adjacency matrix is:

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

Algebraic invariant Value Explanation
characteristic polynomial As complete bipartite graph :
minimal polynomial As complete bipartite graph :
rank of adjacency matrix 2 As complete bipartite graph : 2 (independent of )
eigenvalues (roots of characteristic polynomial) 0 (2 times), 2 (1 time), -2 (1 time) As complete bipartite graph : 0 ( times), (1 time), (1 time)

Laplacian matrix

The Laplacian matrix is as follows:

The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

Algebraic invariant Value Explanation
characteristic polynomial As complete bipartite graph :
minimal polynomial As complete bipartite graph :
rank of Laplacian matrix 3 As complete bipartite graph :
eigenvalues (roots of characteristic polynomial) 0 (1 time), 4 (1 time), 2 (2 times) As complete bipartite graph : 0 (1 time), (1 time), (2 times: times as and times as )

Normalized Laplacian matrix

The normalized Laplacian matrix is as follows:

The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

Algebraic invariant Value Explanation
characteristic polynomial As complete bipartite graph :
minimal polynomial As complete bipartite graph : (independent of as long as )
rank of normalized Laplacian matrix 3 As complete bipartite graph :
eigenvalues (roots of characteristic polynomial) 0 (1 time), 2 (1 time), 1 (2 times) As complete bipartite graph : 0 (1 time), 2 (1 time), 1 ( times)

Realization

As Cayley graph

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a symmetric subset of the group of size 2.

Group Choice of symmetric set that is a generating set for which the Cayley graph is this
cyclic group:Z4 cyclic generator and its inverse
Klein four-group two distinct elements of order two

Geometric embeddings

Planar embedding as a square

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

This embedding is nice in a number of ways:

  • It demonstrates that the graph is a planar graph.
  • Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
  • It demonstrates that the graph is a unit distance graph: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
  • It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.