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

1. Lo, Sheng-Ping (1985). "On Edge-Graceful Labelings of Graphs". Congressus Numerantium. 50: 231–241. Zbl 0597.05054.
2. Q. Kuan, S. Lee, J. Mitchem, and A. Wang (1988). "On Edge-Graceful Unicyclic Graphs". Congressus Numerantium. 61: 65–74.CS1 maint: multiple names: authors list (link)
3. L. Lee, S. Lee and G. Murty (1988). "On Edge-Graceful Labelings of Complete Graphs: Solutions of Lo's Conjecture". Congressus Numerantium. 62: 225–233.
4. D. Small (1990). "Regular (even) Spider Graphs are Edge-Graceful". Congressus Numerantium. 74: 247–254.
5. S. Cabaniss, R. Low, J. Mitchem (1992). "On Edge-Graceful Regular Graphs and Trees". Ars Combinatoria. 34: 129–142.CS1 maint: multiple names: authors list (link)