Irregular Labellings of Circulant Graphs

Marcin Anholcer

Published 2011-11-01Version 1

We investigate the \textit{irregularity strength} ($s(G)$) and \textit{total vertex irregularity strength} ($tvs(G)$) of circulant graphs $Ci_n(1,2,...,k)$ and prove that $tvs(Ci_n(1,2,...,k))=\lceil\frac{n+2k}{2k+1}\rceil$, while $s(Ci_n(1,2,...,k))=\lceil\frac{n+2k-1}{2k}\rceil$ except the case when $(n \bmod 4k = 2k+1 \wedge k\bmod 2=1) \vee n=2k+1$ and $s(Ci_n(1,2,...,k))=\lceil\frac{n+2k-1}{2k}\rceil+1$.