Complete bipartite graph

Definition

Suppose $m,n$ are positive integers. The complete bipartite graph $K_{m,n}$ is an undirected graph defined as follows:

1. Its vertex set is a disjoint union of a subset $A$ of size $m$ and a subset $B$ of size $n$
2. Its edge set is defined as follows: every vertex in $A$ is adjacent to every vertex in $B$. However, no two vertices in $A$ are adjacent to each other, and no two vertices in $B$ are adjacent to each other.

Note that $K_{m,n}$ and $K_{n,m}$ are isomorphic, so the complete bipartite graph can be thought of as parametrized by unordered pairs of (possibly equal, possibly distinct) positive integers.

Explicit descriptions

Adjacency matrix

If we order the vertices so that $A$ makes up the first $m$ vertices and $B$ makes up the last $n$ vertices, the adjacency matrix looks like the block matrix below:

$\left(\begin{array}{cc}{0}_{m\times m}& E_{m\times n}\\ E_{n\times m}& 0_{n\times n}\\ \end{array}\right)$

Here, $0_{a\times b}$ is shorthand for the $a\times b$ matrix with 0s for all its entries and $E_{a\times b}$ is shorthand for the $a\times b$ matrix with 1s for all its entries.

Particular cases

• One special case of interest is where $min\{m,n\}=1$. This case of interesting because in this case, the graph becomes a tree.
• Another case of interest is where $m=n$. This case is interesting because the graph acquires additional symmetry and becomes a vertex-transitive graph.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$m+n$	Follows from definition as disjoint union of subsets of size $m,n$
size of edge set	$mn$	Follows from definition: the edges correspond to choosing one element each from $A$ (size $m$) and $B$ (size $n$)

Numerical invariants associated with vertices

Note that if $m=n$, the graph is a vertex-transitive graph, but if $m\ne n$, the graph is not a vertex-transitive graph.

Function	Value	Explanation
degree of a vertex	$n$ for vertices in $A$ $m$ for vertices in $B$
eccentricity of a vertex	For vertices in $A$: 1 if $m=1$, 2 if $m>1$ For vertices in $B$: 1 if $n=1$, 2 if $n>1$

Other numerical invariants

Function	Value	Explanation
clique number	2	Follows from being non-empty and bipartite
independence number	$max\{m,n\}$	$A$ and $B$ are the only maximal independent sets, so the larger among their sizes gives the independence number.
chromatic number	2	Follows from being non-empty and bipartite
radius of a graph	1 if $min\{m,n\}=1$ 2 if $min\{m,n\}>1$	Follows from computation of eccentricity of each vertex above
diameter of a graph	1 if $max\{m,n\}=1$ 2 if $max\{m,n\}>1$	Follows from computation of eccentricity of each vertex above
odd girth	infinite	follows from being bipartite
even girth	infinite if $min\{m,n\}=1$ 4 if $min\{m,n\}>1$
girth of a graph	infinite if $min\{m,n\}=1$ 4 if $min\{m,n\}>1$

Algebraic theory

Adjacency matrix

If we order the vertices so that $A$ makes up the first $m$ vertices and $B$ makes up the last $n$ vertices, the adjacency matrix looks like the block matrix below:

$\left(\begin{array}{cc}{0}_{m\times m}& E_{m\times n}\\ E_{n\times m}& 0_{n\times n}\\ \end{array}\right)$

Here, $0_{a\times b}$ is shorthand for the $a\times b$ matrix with 0s for all its entries and $E_{a\times b}$ is shorthand for the $a\times b$ matrix with 1s for all its entries.

We can thus compute various algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^{m+n}-mn{t}^{m+n-2}=t^{m+n-2}(t^2-mn)$
minimal polynomial	if $m+n>2$: $t^3-mnt=t(t^2-mn)$ if $m=n=1$: $t^2-mn$
rank of adjacency matrix	2
eigenvalues (roots of characteristic polynomial)	0 (multiplicity $m+n-2$), $\sqrt{mn}$ (multiplicity 1), $-\sqrt{mn}$ (multiplicity 1)

Laplacian matrix

The Laplacian matrix, defined as the matrix difference of the degree matrix and adjacency matrix, looks as follows:

$\left(\begin{array}{cc}n{I}_{m\times m}& -E_{m\times n}\\ -E_{n\times m}& m{I}_{n\times n}\\ \end{array}\right)$

Here, $I$ denotes the identity matrix of the given (square) dimensions, and $E$ denotes the matrix with all entries one.

We can thus compute various algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t(t-(m+n))(t-m{)}^{n-1}(t-n{)}^{m-1}$
minimal polynomial	If $m\ne n$ and both are greater than 1: $t(t-m)(t-n)(t-(m+n))$ If $m=n>1$: $t(t-m)(t-2m)$ If $m=1,n>1$: $t(t-1)(t-(n+1))$ If $m>1,n=1$: $t(t-1)(t-(m+1))$
rank of Laplacian matrix	$m+n-1$
eigenvalues (roots of characteristic polynomial)	0 (1 time), $m+n$ (1 time), $m$ ($n-1$ times), $n$ ($m-1$ times). If $m=1$, $n$ disappears as an eigenvalue. If $n=1$, $m$ disappears as an eigenvalue.

Normalized Laplacian matrix

The normalized Laplacian matrix is as follows:

$\left(\begin{array}{cc}{I}_{m\times m}& (-1/\sqrt{mn})E_{m\times n}\\ (-1/\sqrt{mn})E_{n\times m}& I_{n\times n}\\ \end{array}\right)$

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	$t(t-2)(t-1{)}^{m+n-2}$ Note that when $m=n$, this simplifies to $t(t-2)(t-1{)}^{2(m-1)}$
minimal polynomial	If $m+n>2$: $t(t-1)(t-2)$ If $m=n=1$: $t(t-2)$
rank of normalized Laplacian matrix	$m+n-1$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 2 (1 time), 1 ($m+n-2$ times) Note that the eigenvalue 1 disappears if $m=n=1$