# Square graph

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

## Contents

## Definition

This undirected graph, called the **square graph**, is defined in the following equivalent ways:

- It is the cycle graph on 4 vertices, denoted .
- It is the complete bipartite graph
- It is the 2-dimensional hypercube graph.
- 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.