Elegant labelings and Edge-colorings

Abstract

A graph $G=(V,E)$ is said to be elegant if it is possible to label its vertices by an injective mapping $g$ into $\{0,1,\dots ,|E|\}$ such that the induced labeling $h$ on the edges defined for edge $x,y$ by $h(x,y)=g(x)+g(y)\mathrm{mod}(|E|+1)$ takes all the values in $\{1,\dots ,|E|\}$. In the first part of this paper, we prove the existence of a coloring of $K_n$ with a omnicolored path on $n$ vertices as subgraph, which had been conjectured by Hastman [2].
In the second part we prove that the cycle on $n$ vertices is elegant if and only if $n\ne 1(\mathrm{mod}4)$ and we give a new construction of an elegant labeling of the path $P_n$, where $n\ne 4$.