Elegant Labeled Graphs

Abstract

An {\it elegant labeling} $f$ of a graph $G$ with $m$ edges is an injective function from the vertices of $G$ to the set $\{0, 1, 2,\dots, m\}$ such that when each edge $xy$ is assigned the label $f(x) + f(y) (\mod m+1)$, the resulting edge labels are distinct and non zero.

In this paper we prove the following results

1. The graph $P_n^2$ is elegant, for all $n \geq 1$.
2. The graphs $P_m^2 + \overline{K}_n$, $S_m + S_n$ and $S_m + \overline{K}_m$ are elegant, for all $m, n \geq 1$.
3. Every even cycle $C_{2n} : <a_0, a_1, \dots, a_{2n-1}, a_0>$ with $2n-3$ chords $a_0a_2, a_0a_3, \dots, a_0a_{2n-2}$ is elegant, for all $n \geq 2$.
4. The graph $C_3 \times P_m$ is elegant, for all $m \geq 1$.