Irregular Labellings of Circulant Graphs

Abstract

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

I already had submitted this paper when Cory Palmer suggested that the main proofs may be simplified. Our common paper is still in preparation (to appear in Discrete Mathematics, we hope). However, I decided to publish the original version here, as some ideas included in it are supposed to be used in my further works. On the other hand, maybe someone else would like to use it

References in corpus (1)

• Total Vertex Irregularity Strength of Forests