On Irregular Total and Graceful Labelings

Abstract

A graph labeling is an assignment of integer label to the elements of graph in such a way that some certain conditions are satisfied. If the domain set consists only vertices (or edges) then it is called vertex (or edge) labeling respectively. If the domain set consists vertices and edges then it is called total labeling. A graceful labeling of a (p, q)-graph is an injection f from the set of vertices to the set {1, 2, . . . , q + 1} such that each edge uv is assigned the label |f (u) − f (v)|, the resulting edge labels are distinct. Moreover if f has the property that there exists an integer λ such that for each edge uv either f (u) ≤ λ < f (v) or f (v) ≤ λ < f (u) then f is called an α-labeling. A one-to-one map taking the vertices on the integers 1, 2, 3, . . . , p with the property that the edge weight (sum of end points labels ) form an arithmetic progression starting from a and having common difference d, is called (a, d)-edge antimagic vertex labeling. A total k-labeling of a graph G is a labeling from the set of vertices and edges to the set {1, 2, . . . , k}. A total k-labeling is defined to be an edge irregular total k-labeling of the graph G if edge weights are different for all pairs of distinct edges. The minimum value of k for which the graph G has an edge irregular total k- labeling is called the total edge irregularity strength of the graph G, denoted by tes(G). In this thesis, we construct an α-labeling of trees from graceful labeling of smaller trees and using a connection between α-labeling and edge antimagic vertex labeling we obtain a super (a, d)-edge antimagic total labeling of trees. Moreover we present new results on the total edge irregularity strength.