Antimagic labelings of graphs and digraphs

By a graph G = (V,E), we mean a finite, undirected graph with neither loops nor multiple edges and without isolated vertices. The order |V | and the size |E| of G are denoted by p and q respectively. For graph theoretic terminology we refer to Chartrand and Lesniak [19]. Graph labeling is one major research area in graph theory. New results are being discovered and published at a rapidly increasing rate. Further we have an enormous number of open problems and conjectures on graph labelings. For an excellent and up to date dynamic survey on graph labeling we refer to Gallian [23]. Most of the graph labeling methods trace their origin to the concept of β-valuation introduced by Rosa [32]. The same concept was introduced by Golomb who called it a graceful labeling [24]. Various types of graph labelings such as graceful labeling, harmonious labeling, equitable labeling, cordial labeling, arithmetic labeling, Skolem graceful labeling, set labeling, magic labeling, antimagic labeling, set-magic labeling, Σ-labeling, α-labeling, multiplicative and strongly multiplicative labeling, prime labeling, mean labeling and orthogonal labeling have been investigated by several authors. The concept of graph labeling has a wide range of applications to other branches of science such as X-ray crystallography, coding theory, cryptography, astronomy, circuit design and communication networks design. Informally, by a graph labeling we mean an assignment of numbers to graph elements such as vertices or edges or both subject to some conditions. These conditions are normally expressed on the basis of some values (weights) of an evaluating function. One situation is all the vertex weights or all the edge weights are same. In such case we call the labeled graph as vertex magic or edge magic respectively. Another situation is all the vertex weights or edge weights are different. In such case we call the graph as vertex antimagic or edge antimagic respectively. For an exhaustive study on magic labelings we refer to the book by Wallis [41]. A variety of antimagic labelings with lot of open problems are given in Baca and Miller [10]. Hefetz et al. [27] studied antimagic labeling in digraphs. In this thesis we concentrate mainly on two types of antimagic labelings of graphs and antimagic labelings of digraphs. The notion of antimagic labeling was introduced by Hartsfield and Ringel [26] in 1990. A graph G is antimagic if the edges of G can be labeled by the numbers 1, 2, 3, . . . , q such that the sums of the labels of the edges incident to each vertex (called weight of a vertex) are distinct. Also they conjectured that every connected graph different from K2 is antimagic. This conjecture is still open. Even if we restrict ourselves to trees, it is not known