A Metaheuristic Approach to the Graceful Labeling Problem

Graceful Labeling Problem

In graph theory, a graceful labeling of a graph G = (V, E) with n vertices and m edges is a labeling of its vertices with distinct integers between 0 and m inclusive, such that each edge is uniquely identified by the absolute difference between its endpoints. To be more precise, if we assume G = (V, E) to be an undirected graph without loops or double connections between vertices, a graceful labeling of G, with n vertices and edges, is a one-to-one mapping f of the vertex set V into the set {0, 1, 2, ..., m}, so that if we assign an edge label | f(x) - f(y) | to any edge (x, y), each edge receives a distinct positive integer label. A graph that can be gracefully labeled is called a graceful graph (Rosa, 1967). A sample graceful graph is shown in Figure 1. Vertex labels are shown inside the vertex circles, and edge labels are shown in red near the related edges.

Figure 1.

An example of graceful labeling of a graph

The name “graceful labeling” is due to Solomon W. Golomb; however, this class of labelings was originally given the name β-labelings by Alex Rosa in a 1967 paper on graph labeling (Rosa, 1967). The computational complexity of the graceful labeling problem is not known, but a related problem called harmonious labeling was shown to be NP-complete (Gallian, 2009). In fact, the graceful labeling problem is rather a well-known example of the problems in NP, which are not known to be NP-complete, and neither known to be in P (Johnson, 2005). Many variations of graph labeling have been introduced in recent years by researchers. Various classes of graphs have been proven mathematically to be graceful or non-graceful. A detailed survey of graph labeling problems and the related results are shown in a survey by Gallian (2009). There is an unproved conjecture that all trees are graceful. Although, it is shown that trees with up to 27 vertices are graceful. It is shown that all cycles C_n are graceful if and only if n ≡ 0 or 3 (mod 4). All wheels W_n, Helms H_n, and Crowns R_n are graceful. The complete graphs K_n are graceful if and only if n ≤ 4. The necessary condition for a windmill K_n^(m) (n ≥ 3) to be graceful is that n ≤ 5; a windmill K_n^(m) consists of m complete graphs K_n with one common vertex (Gallian, 2009). An example for each class of the graphs mentioned above and their graceful labelings are shown in Figure 2.

Figure 2.

Examples for some classes of graceful graphs and their graceful labelings: (a) a cycle C₇, (b) a tree T₁₀, (c) a wheel W₄, (d) a helm H₅, (e) a crown R₅, (f) a windmill K₃⁽⁴⁾

The graceful labeling problem is to find out whether a given graph is graceful or not, and if it is, how to label the vertices. The process of gracefully labeling a graph is a very tedious and difficult task for many classes of graphs (Eshghi & Azimi, 2004).