On $\sigma$-Labeling the Union of Three Cycles

Abstract

Let $G$ be a graph of size $n$ with vertex set $V(G)$ and edge set $E(G)$. A $\sigma$-labeling of $G$ is a one-to-one function $f:V(G)\to \{0,1,\dots ,2n\}$ such that $\{|f(u)–f(v)|:\{u,v\}\in E(G)\}=\{1,2,\dots ,n\}$. Such a labeling of $G$ yields cyclic $G$-decompositions of $K_{2n+1}$ and of $K_{2n+2}–F$, where $F$ is a $1$-factor of $K_{2n+2}$. It is conjectured that a $2$-regular graph of size $n$ has a $\sigma$-labeling if and only if $n\equiv 0$ or $3(\mathrm{mod}4)$. We show that this conjecture holds when the graph has at most three components.