\(k\)-equitable Labellings of Cycles and Some Other Graphs

In this thesis we examine the \(k\)-equitability of certain graphs. We prove the following: The path on \(n\) vertices, \(P_n\), is \(k\)-equitable for any natural number \(k\). The cycle on \(k\) vertices, \(C_n\), is \(k\)-equitable for any natural number \(k\), if and only if all of the following conditions hold:\(n \neq k\); if \(k \equiv 2, 3 \pmod{4}\) then \(n \neq k-1\);if \(k \equiv 2, 3 \pmod{4}\) then \(n \not\equiv k\pmod{2k}\) The only \(2\)-equitable complete graphs are \(K_1\), \(K_2\), and \(K_3\).
The complete graph on \(n\) vertices, \(K_n\), is not \(k\)-equitable for any natural number \(k\) for which \(3 \leq k < n\). If \(k \geq n\), then determining the \(k\)-equitability of \(K_n\) is equivalent to solving a well-known open combinatorial problem involving the notching of a metal bar.The star on \(n+1\) vertices, \(S_n\), is \(k\)-equitable for any natural number \(k\). The complete bipartite graph \(K_{2,n}\) is \(k\)-equitable for any natural number \(k\) if and only if \(n \equiv k-1 \pmod{k}\); or \(n \equiv 0, 1, \ldots, [ k/2 ] – 1 \pmod{k}\);or \(n = \lfloor k/2 \rfloor\) and \(k\) is odd.