Edge-graceful labeling explained

In graph theory, an edge-graceful labeling is a type of graph labeling for simple, connected graphs in which no two distinct edges connect the same two distinct vertices and no edge connects a vertex to itself.

Edge-graceful labelings were first introduced by Sheng-Ping Lo in his seminal paper.[1]

Definition

Given a graph, we denote the set of its edges by and that of its vertices by . Let be the cardinality of and be that of . Once a labeling of the edges is given, a vertex of the graph is labeled by the sum of the labels of the edges incident to it, modulo . Or, in symbols, the induced labeling on a vertex is given by

V(u)=\SigmaE(e)\mod|V(G)|

where is the resulting value for the vertex and is the existing value of an edge incident to .

The problem is to find a labeling for the edges such that all the labels from to are used once and that the induced labels on the vertices run from to . In other words, the resulting set of labels for the edges should be

Notes and References

  1. 0597.05054 . Lo . Sheng-Ping . On Edge-Graceful Labelings of Graphs . Sundance Conference, Utah . Congressus Numerantium . 50 . 1985 . 231–241 .