Almost-magic, relaxed-magic and magic strength of a graph

Abstract

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 HT_n, Twigs TW_n (n is odd) and almost-magic strength of nP₂ (n is even) and Twigs TW_n (n is even). Also, we obtain the bounds for the magic strength of path-union P_n(m) and relaxed-magic strength of kS_n and kP_n.