4
$\begingroup$

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!

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

Complete bipartite graph K(2,1)

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

K(2,1) after swapping the labels u_1 with u_2

...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...

K(2,1) after swapping the labels u_1 with v_1

...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\}$):

Complete bipartite graph K(4,3)

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?
$\endgroup$
1
  • $\begingroup$ Bonus question: What if $|U| = |V|$? $\endgroup$
    – Kevin
    Jul 4 at 17:51
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.