Super Edge-Magic Deficiency of Forests

Abstract

A labeling of a graph is a mapping that carries some set of graph elements (vertices, edges or both) into numbers (usually positive integers). An edge-magic total labeling of a graph with p vertices and q edges is a one-to-one mapping that takes the vertices and edges onto the integers 1, 2, . . . , p + q, so that the sums of the label on the edges and the labels of their end vertices are always the same, thus they are independent any particular edge. Such a labeling is called super if the p smallest possible labels appear at the vertices. In 1970 Kotzig and Rosa [33] introduced the concept of edge-magic deficiency of a graph G, denoted by μ(G), which is the minimum nonnegative integer n such that G ∪ nK 1 is edge-magic total. Motivated by Kotzig and Rosa’s concept of edge-magic deficiency, Figueroa-Centeno, Ichishima and Muntaner-Batle [17] defined a similar concept for super edge-magic total labelings. The super edge-magic deficiency of a graph G, which is denoted by μ s (G), is the minimum nonnegative integer n such that G ∪ nK 1 has a super edge-magic total labeling or it is equal to ∞ if there exists no such n. The thesis is devoted to study of super edge-magic deficiency of forests. We present new results on the super edge-magic deficiencies of forests including union of paths, stars, comb, banana trees and subdivisions of K 1,3 . In the thesis we also deal with the super edge-magic deficiencies of forests formed by a disjoint union of stars.