**Originators:** Tao-Ming Wang, Cheng-Chih Hsiao, Sin-Min Lee:
(presented by Hehui Wu - REGS 2009)

**Definitions:** For a nonnegative integer *k*, a graph *G*
with *n* vertices and *m* edges is *k-edge-graceful* if there
is a bijection *f: E(G)→{k,k+1,&hellip,k+m-1}* such that the function
*f ^{+}: V(G)→Z_{n}* is also a bijection, where

For a graph *G*, the square of *G*, written *G ^{2}*,
is the graph with vertex set

**Background:** Edge-graceful labeling was introduced by S. Lo [L3].
It is an analogue of the well-known concept of graceful labeling. An
introduction to graceful labeling appears on Wikipedia [W]. A huge amount of
information on graceful labeling and other types of graph labeling problems can
be found in the dynamic survey by Gallian [Ga].

**Conjecture 1:** (Lee [L1]) Every tree with odd order is edge-graceful.

**Comment:** This is the edge-graceful labeling version of the famous
Ringel-Kotzig Graceful Tree Conjecture. The necessary condition below
requires *n(n-1)/2* to be divisible by *n* for an *n*-vertex
tree to be edge-graphs, and this never happens when *n* is even.

**Conjecture 2:** (Lee [L2]) A connected graph with *n* vertices
and *m* edges is edge-graceful if and only if
*m(m+1)≡n(n-1)/2* (mod *n*).

**Comment:** Lo [L3] noticed that this condition is necessary for the
existence of an edge-graceful labeling; the condition is called Lo's Condition.
It follows by summing the edge labels at each vertex in an edge-graceful
labeling and grouping the total by edges and by vertices.
Sufficiency has been proved for some special classes of graphs, including
maximal outerplanar graphs (Lee-Kitagaki-Young-Kocay [LKYK]), complete
multipartite graphs with equal part-sizes (Lee-Seah [LS1]), powers of
cycles (Lee-Seah [LS2]), and powers of paths (Shiu-Lam-Cheng [SLC]).

**Conjecture 3:** (Wang-Hsiao-Lee [WHL]) A connected graph with *n*
vertices and *m* edges is *k*-edge-graceful if and only if
*m(m+2k-1)&equiv n(n-1)/2* (mod *n*).

**Comment:** Conjecture 3 generalizes Conjecture 2; necessity follows in
the same way. When a graph is regular, the necessary condition for
*k*-edge-graceful labelings holds if and only if Lo's Condition holds.
The general condition is sufficient for existence of *k*-edge-graceful
labelings of *P _{r}^{2}* when

**Question 4:** (Wang-Hsiao-Lee [WHL]) Determine the edge-graceful
spectrum for *P _{r}^{2}* when

**Comment:** If the condition in Conjecture 3 is sufficient for a graph
*G*, one may describe this by saying that the edge-graceful spectrum of
*G* is *full* One may consider Conjecture 3 and Question 4 for other
natural classes of graphs, such as higher powers of paths, grids, etc.

**References:**

[Ga] J.A. Gallian, A dynamic survey of graph labeling, The Electronic
Journal of Combinatorics DS6 (2009), Ninth Version, January 31, 2009, 219 pages.

[L1] S.-M. Lee, A conjecture on edge-graceful trees, Scientia, 3 (1989)
45-47.

[L2] S.-M. Lee, New directions in the theory of edge-graceful graphs, Proc. 6th Caribbean Conf. Combin. & Computing (1991) 216-231.

[LKYK] S.-M. Lee, M. Kitagaki, J. Young, and W. Kocay, On edge-graceful and
edge-magic maximal outerplanar graphs, J. Combin. Math. Combin. Comput., 59
(2006) 119-129.

[LS1] S.-M. Lee and E. Seah, Edge-gracefulness labelings of regular
complete K-partite graphs, Congr. Numer., 75 (1990) 41-50.

[LS2] S.-M. Lee and E. Seah, On edge-gracefulness of kth power cycles,
Congr. Numer., 71 (1990) 237-242.

[L3] S. Lo, On Edge-Graceful labelings of graphs, Congressus Numerantium
50 (1985) pp.231-241

[SLC] W. C. Shiu, P. C. B. Lam, and H. L. Cheng, Edge-gracefulness of the
composition of paths with the null graphs, Discrete Math., 253 (2002) 63-76.

[WHL] Wang, Tao-Ming; Hsiao, Cheng-Chih; Lee, Sin-Min; A note on
edge-graceful spectra of the square of paths. Discrete Math. 308 (2008),
no. 23, 5878--5885.

[W] http://en.wikipedia.org/wiki/Graceful_labeling