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.

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\neq 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$