What is the automorphism group of a complete bipartite graph?

Question

Let $m, n \in \mathbb{N}$ with $m \ne n$. Determine the automorphism group of the complete bipartite Graph $\mathcal{V}_{m,n}$.

Some definitions: A complete bipartite graph is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$, that is every edge connects a vertex in $U$ to one in $V$. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

My idea: In need to find an appropriate characterization of the larger set in the bipartite decomposition, but I am not sure.

An old exam question I am looking at to learn for my upcoming discrete math exam. I unfortunately am not sure what to do. Thanks in advance!

Answer 1

An automorphism of the complete bipartite graph $\mathcal{V}_{m,n}$ with $m\neq n$ must permute the vertices of each side of the bipartite graph independently. Therefore we can write an automorphism as $(\phi,\psi)$ were $\phi$ permutes $m$ vertices and $\psi$ permutes $n$ vertices. Writing two automorphisms as $(\phi_1,\psi_1)$ and $(\phi_2,\psi_2),$ their composite will be given by $(\phi_1\circ \phi_2,\psi_1\circ \psi_2).$ Therefore the automorphism group is $S_m\times S_n$ where $S_m$ and $S_n$ are permutation groups.

Answer 2

Are you familiar with graph automorphisms? We have a labelled graph, and permute its labels using some permutation $\alpha$: if the result is the same graph (i.e., vertices are adjacent in the permuted graph if and only if they are adjacent in the original graph) then $\alpha$ is an automorphism.

So in the above graph, if we swap the labels $u_1$ and $u_2$, then...

...the graph remains the same ($u_1$ and $u_2$ are both adjacent to $v_1$, and $u_1$ and $u_2$ are not adjacent); the permutation which swaps $u_1$ and $u_2$ is an automorphism.

But if we swap the labels $u_1$ and $v_1$ in our original graph, then...

...the graph does not remain the same ($u_1$ and $u_2$ are adjacent after applying this permutation); the permutation which swaps $u_1$ and $v_1$ is not an automorphism.

An example of a complete bipartite graph is (we can label the vertices however we like; usually one side is $\{u_i\}$ and one side is $\{v_i\}$):

The key observation we're meant to make here is: How many neighbors do the vertices have? (I.e., vertex degree.)

Vertex degree is an example of an invariant: if we apply an automorphism which maps a vertex a to vertex b then a and b have the same degree. (Otherwise it wouldn't be an automorphism---vertex a couldn't have the same adjacencies afterwards.) The contrapositive of this is: if vertex u and vertex v do not have the same degree, then no automorphism maps u to v.

(While it's true that bipartite graphs don't have odd-length cycles, it's not useful for this problem.)

So...

• What are the vertex degrees in $U$? (I.e., how many neighbors do vertices in $U$ have?)
• What are the vertex degrees in $V$? (I.e., how many neighbors do vertices in $V$ have?)
• Why does this imply automorphisms do not permute vertices in $U$ to vertices in $V$?
• Provided we permute vertices in $U$ to vertices in $U$ and vertices in $V$ to vertices in $V$, do we always get an automorphism?