Set-Valuations of Graphs and Their Applications

Introduction

Labeling is a term used in technical sense for naming objects using symbolic format drawn from any universe of discourse such as the set of numbers, algebraic groups or the power set of a ‘ground set’ X. The objects requiring labeling could come from a variety of fields of human interest such as chemical elements, radio antennae, spectral bands and plant/animal species. Further, categorization of objects based on certain clustering rules might lead to derived labels from the labels of objects in each cluster; for instance labels a and b of two individual elements in a dyad {A,B} could be used to derive a labeling for the dyad in a way that could reflect a relational combination of the labels a and b. To be specific, A and B are assigned labels a,b from an algebraic group, whence the dyad {A,B} is assigned the label a*b where * is the group operation. Such assignments are generally motivated by a need to optimize on the number of symbols used to label the entire discrete structure so that the structure could be effectively encoded for handling its computerized analysis. In general, graph labelings, where the basic elements (i.e., vertices and/or edges) of a graph are assigned elements of a given set or subsets of a nonempty ‘ground set’ subject to given conditions, have often been motivated by practical considerations such as the one mentioned above. They are also of theoretical interest on their own right. ‘Graph labeling’ as an independent notion using numbers was first introduced in the mid sixties. Most graph labeling methods trace their origin to one introduced by Rosa (1967).

Even though the study of graceful graphs and graceful labeling methods was introduced by Rosa (1965) the term graceful graph was used first by Golomb (1972). Rosa (1965) defined a β-valuation of a (p,q)-graph G as an injection f from the vertices of G to the set {0,1,…,q−1} such that, when each edge xy is assigned the label |f(x)−f(y)|, the resulting edge labels are all distinct. In a graceful labeling of a graph G the resulting edge labels must be distinct and take values 1,2,…,q. The study of graceful labelings of a graph is a prolific area of research in graph theory. The graceful labeling problem is to determine which graphs are graceful. Proving a graph G is or is not graceful involves either producing a graceful labeling of G or showing that G does not admit a graceful labeling. While the graceful labeling of graphs is perceived to be a primarily theoretical topic in the field of graph theory, gracefully labelled graphs often serve as models in a wide range of applications. Such applications include coding theory and communication network addressing. Bloom and Golomb (1977) give a detailed account of some of the important applications of gracefully labelled graphs. That ‘all trees are graceful’ is a long-standing conjecture known as the “Ringel–Kotzig Conjecture” (Acharya, Rao & Arumugam, 2008).