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.
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
:<math>V(u)=\Sigma E(e) \mod |V(G)|</math>
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 , each value being used once, and that for the vertices should be .
A graph is said to be edge-graceful if it admits an edge-graceful labeling.
Examples
Cycles
150px|thumb|An edge-graceful labeling of
Consider the cycle with three vertices, . 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, is edge-graceful when is odd and not when is even.
Paths
Consider a path with two vertices, . 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 is not edge-graceful.
Appending an edge and a vertex to gives , the path with three vertices. Denote the vertices by , , and . Label the two edges in the following way: the edge is labeled 1 and labeled 2. The induced labelings on , , and are then 1, 0, and 2 respectively. This is an edge-graceful labeling and so is edge-graceful.
Similarly, one can check that is not edge-graceful.
In general, is edge-graceful when 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 with edges and vertices to be edge-graceful: This follows from the fact that the sum of the labels of the vertices is twice the sum of the edges, modulo . 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 <math>S_m</math> (a central node and m legs of length 1) is edge-graceful when m is even and not when m is odd.
- The friendship graph <math>F_m</math> is edge-graceful when m is odd and not when it is even.
- Regular trees, <math>T_{m,n}</math> (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.
- The complete graph on n vertices, <math>K_n</math>, is edge-graceful unless n is singly even, <math>n=2\mod 4</math>.
- The ladder graph is never edge-graceful.