A Metaheuristic Approach to the Graceful Labeling Problem

A Metaheuristic Approach to the Graceful Labeling Problem

Houra Mahmoudzadeh (Sharif University of Technology, Iran) and Kourosh Eshghi (Sharif University of Technology, Iran)
Copyright: © 2010 |Pages: 15
DOI: 10.4018/jamc.2010100103

Abstract

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. In this paper, the well-known graceful labeling problem of graphs is represented as an optimization problem, and an algorithm based on Ant Colony Optimization metaheuristic is proposed for finding its solutions. In this regard, the proposed algorithm is applied to different classes of graphs and the results are compared with the few existing methods inside of different literature.
Article Preview

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 Cn are graceful if and only if n ≡ 0 or 3 (mod 4). All wheels Wn, Helms Hn, and Crowns Rn are graceful. The complete graphs Kn are graceful if and only if n ≤ 4. The necessary condition for a windmill Kn(m) (n ≥ 3) to be graceful is that n ≤ 5; a windmill Kn(m) consists of m complete graphs Kn 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 C7, (b) a tree T10, (c) a wheel W4, (d) a helm H5, (e) a crown R5, (f) a windmill K3(4)

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).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing