Elegant Labeled Graphs
Aarthi Elumalai, G. Sethuraman · Journal of Informatics and Mathematical Sciences · 2010
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 resultsThe graph $P_n^2$ is elegant, for all $n \geq 1$.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$.Every even cycle $C_{2n} : $ with $2n-3$ chords $a_0a_2, a_0a_3, \dots, a_0a_{2n-2}$ is elegant, for all $n \geq 2$.The graph $C_3 \times P_m$ is elegant, for all $m \geq 1$.