Elegant Labeled Graphs - Elumalai, A.; Sethuraman, G. (Journal of Informatics and Mathematical Sciences, 2010)
An 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,…, m} such that when each edge xy is assigned the label f(x) + f(y) (m+1), the resulting edge labels are distinct and non zero. In this paper we prove the following results The graph P_n^2 is elegant, for all n ≥ 1. The graphs P_m^2 + K_n, S_m + S_n and S_m + K_m are elegant, for all m, n ≥ 1. Every even cycle C_2n : <a_0, a_1, …, a_2n-1, a_0> with 2n-3 chords a_0a_2, a_0a_3, …, a_0a_2n-2 is elegant, for all n ≥ 2. The graph C_3 × P_m is elegant, for all m ≥ 1.