Edge-graceful labeling

In graph theory, an edge-graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the graph is connected. Edge-graceful labelings were first introduced by Sheng-Ping Lo in his seminal paper.^[1]

Definition[]

Given a graph G, we denote the set of edges by ${\displaystyle E(G)}$ and the vertices by ${\displaystyle V(G)}$. Let q be the cardinality of ${\displaystyle E(G)}$ and p be that of ${\displaystyle V(G)}$. Once a labeling of the edges is given, a vertex u 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 the vertex u is given by

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

where V(u) is the label for the vertex and E(e) is the assigned value of an edge 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 the induced labels on the vertices run from 0 to ${\displaystyle p-1}$. In other words, the resulting set for labels of the edges should be ${\displaystyle \{1,2\dots q\}}$ and ${\displaystyle \{0,1\dots p-1\}}$ for the vertices.

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

Examples[]

Cycles[]

An edge-graceful labeling of ${\displaystyle C_{5}}$

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, ${\displaystyle C_{m}}$ is edge-graceful when m is odd and not when m is even.^[2]

Paths[]

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.

A necessary condition[]

Lo gave a necessary condition for a graph to be edge-graceful.^[1] It is that a graph with q edges and p vertices is edge graceful only if

${\displaystyle \;q(q+1)}$ is congruent to ${\displaystyle {\frac {p(p-1)}{2}}}$ modulo p.

or, 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.

Further selected results[]

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

References[]