Edge-graceful labeling

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]

Given a graph G, we denote the set of its edges by E(G) and that of its vertices by V(G). Let q be the cardinality of E(G) and p be that of V(G). 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 p. Or, in symbols, the induced labeling on a vertex is given by

${\displaystyle V(u)=\Sigma E(e)\mod |V(G)|}$

where V(u) is the resulting value for the vertex u and E(e) is the existing value of an edge e incident to u.

The problem is to find a labeling for the edges such that all the labels from 1 to q are used once and that the induced labels on the vertices run from 0 to p – 1. In other words, the resulting set of labels for the edges should be {1, 2, …, q}, each value being used once, and that for the vertices should be {0, 1, …, p – 1}.

A graph G is said to be edge-graceful if it admits an edge-graceful labeling.

Consider the cycle with three vertices, C₃. This is simply a triangle. One can label the edges 1, 2, and 3, and check directly that, along with the induced labeling on the vertices, this gives an edge-graceful labeling. Similar to paths, C_m is edge-graceful when m is odd and not when m is even.^[2]

Consider a path with two vertices, P₂. Here the only possibility is to label the only edge in the graph 1. The induced labeling on the two vertices are both 1. So P₂ is not edge-graceful.

Appending an edge and a vertex to P₂ gives P₃, the path with three vertices. Denote the vertices by v₁, v₂, and v₃. Label the two edges in the following way: the edge (v₁, v₂) is labeled 1 and (v₂, v₃) labeled 2. The induced labelings on v₁, v₂, and v₃ are then 1, 0, and 2 respectively. This is an edge-graceful labeling and so P₃ is edge-graceful.

Similarly, one can check that P₄ is not edge-graceful.

In general, P_m is edge-graceful when m is odd and not edge-graceful when it is even. This follows from a necessary condition for edge-gracefulness.

Lo gave a necessary condition for a graph with q edges and p vertices to be edge-graceful:^[1]q(q + 1) must be congruent to ⁠p(p – 1)/2⁠ mod p. In symbols:

${\displaystyle q(q+1)\equiv {\frac {p(p-1)}{2}}\mod p.}$

This is referred to as Lo's condition in the literature.^[3] This follows from the fact that the sum of the labels of the vertices is twice the sum of the edges, modulo p. This is useful for disproving a graph is edge-graceful. For instance, one can apply this directly to the path and cycle examples given above.

• The Petersen graph is not edge-graceful.
• The star graph ${\displaystyle S_{m}}$ (a central node and m legs of length 1) is edge-graceful when m is even and not when m is odd.^[4]
• The friendship graph ${\displaystyle F_{m}}$ is edge-graceful when m is odd and not when it is even.
• Regular trees, ${\displaystyle T_{m,n}}$ (depth n with each non-leaf node emitting m new vertices) are edge-graceful when m is even for any value n but not edge-graceful whenever m is odd.^[5]
• The complete graph on n vertices, ${\displaystyle K_{n}}$, is edge-graceful unless n is singly even, ${\displaystyle n=2\mod 4}$.
• The ladder graph is never edge-graceful.