\(k\)-Equitable Labelings of Complete Bipartite and Multipartite Graphs

Let \(G = G(V, E)\) be a graph. A labeling of \(G\) is a function \(f: V \to \{0, 1, \ldots, n\}\) such that for each edge \(e = (u, v) \in E\), \(f(e) = |f(u) – f(v)|\). Such a labeling is said to be \(k\)-equitable if it is a labeling of the vertices with the numbers \(0\) through \(k – 1\) such that, if \(v_i\) is the number of vertices labeled \(i\), and \(e^i\) is the number of edges labeled \(i\), then \(|v^i – v^j| < 1\) and \(|e^i – e^j| \leq 1\) for all \(i, j\). A graph is said to be \(k\)-equitable if it has a \(k\)-equitable labeling. In this paper, we characterize the \(k\)-equitability of complete bipartite graphs and consider the equitability of complete multipartite graphs.