Elegant Labeled Graphs

A. Elumalai, G. Sethuraman


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$.


Graph labeling; Elegant labeling; Elegant graphs; Join graphs; Product graphs

Full Text:


DOI: http://dx.doi.org/10.26713%2Fjims.v2i1.26

eISSN 0975-5748; pISSN 0974-875X