Houra Mahmoudzadeh (Sharif University of Technology, Iran) and Kourosh Eshghi (Sharif University of Technology, Iran)

Source Title: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends

Copyright: © 2012
|Pages: 16
DOI: 10.4018/978-1-4666-0270-0.ch013

Chapter Preview

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

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

Examples for some classes of graceful graphs and their graceful labelings: (a) a cycle *C*_{7}, (b) a tree *T*_{10}, (c) a wheel *W*_{4}, (d) a helm *H*_{5}, (e) a crown *R*_{5}, (f) a windmill *K*_{3}^{(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).

Search this Book:

Reset

Copyright © 1988-2020, IGI Global - All Rights Reserved