Edge graceful Labelings (2008)

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)→Zn is also a bijection, where f+(v) ≡ ∑uv∈E(G)f(uv) (mod n). Such a labeling is a k-edge-graceful labeling. The property of being 1-edge-graceful is also called simply edge-graceful.

For a graph G, the square of G, written G2, is the graph with vertex set V(G) in which vertices are adjacent if the distance between them in G is at most 2. In particular, Pr2, the square of an r-vertex path, has vertices v1,...,vr, with vertices adjacent if their indices differ by at most 2.

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 Pr2 when r is odd [WHL]. For even r, it is sufficient when r≤12, and the general case remains open.

Question 4: (Wang-Hsiao-Lee [WHL]) Determine the edge-graceful spectrum for Pr2 when r is even, where the edge-graceful spectrum of a graph G is the set of nonnegative integers k such that G is k-edge-graceful.

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.

[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