Almost-magic, relaxed-magic and magic strength of a graph - Murugan M. (Utilitas Mathematica, 2004)
A (p,q) graph G is said to be magic if there exists a bijection f: V ∪ E → {1,2,..., p + q} such that for all edges xy, f(x) + f(y) + f(xy) is a constant. Such a bijection is called a magic labeling of G. The magic strength of a graph G is denoted by m(G) and is defined as the minimum of all constants where the minimum is taken over all magic labelings of G. In this paper, we introduce almost-magic labeling, relaxed-magic labeling, almost-magic strength and relaxed-magic strength of a graph. We show a magic strength of Huffman tree HTn, Twigs TWn (n is odd) and almost-magic strength of nP2 (n is even) and Twigs TWn (n is even). Also, we obtain the bounds for the magic strength of path-union Pn(m) and relaxed-magic strength of kSn and kPn.