Super Edge Least-Magic Graphs

Abstract

A (p, q)-graph G = (V, E) is said to be super edge-magic if there exists a bijection f fromV ? E to {1, 2, 3,..., p + q } with vertices maps to {1, 2, 3,..., p} such that for all edges uv of G, f(u) + f(v) + f(uv) is a constant and bijection so denned is called a super edge- magic labeling of G, For any super edge-magic labeling of G, there is a constant c(f) such that for all edges uv of G, f(u) + f(v) + f(uv) = c(f) and its range is p + q + 3 ? c(f) ? 3p. In this paper we study super edge-magic graphs with constant c(f) = p+q +3 for at least one f and such graphs are denned as super edge least-magic(SEL-magic) graphs. We investigate the following general results on the structure of SEL-magic graphs including a result, which determines all the regular SEL-magic graphs. (1) A SEL-magic graph is either a forest with exactly one nontrivial component, which is a star or has a triangle. (2) If an eulerian (p,q)-graph G = (V, E) is SEL-magic then q ? 0, 3(mod4). (3) The minimum vertex degree ? of any SEL-monograph is at most 3. (4) There are exactly three nontrivial regular graphs K2,K3 and K2 K3 which are SEL-magic. Also we define level joined planar grid graph L J : Pm Pn and prove that it is SEL-magic. Also we give a general method of constructing new SEL-magic graphs from any given SEL-magic graph. 2005 Elsevier Ltd. All rights reserved.