$k$-equitable Labellings of Cycles and Some Other Graphs

Abstract

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\ne k$; if $k\equiv 2,3(\mathrm{mod}4)$ then $n\ne k-1$;if $k\equiv 2,3(\mathrm{mod}4)$ then $n\not\equiv k(\mathrm{mod}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\le k<n$. If $k\ge 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(\mathrm{mod}k)$; or $n\equiv 0,1,\dots ,[k/2]–1(\mathrm{mod}k)$;or $n=\lfloor k/2\rfloor$ and $k$ is odd.