Edge-magic Indices of (n, n - 1)-graphs¹ 1 Partially supported by Faculty Research Grant of Hong Kong Baptist University.

A graph G = (V, E) with p vertices and q edges is called edge-magic if there is a bijection f : E → {1, 2, ..., q} such that the induced mapping f⁺ : V → Z_p is a constant mapping, where f⁺ (u) ≡ ∑ uv ∈ E f(uv) (mod p). A necessary condition of edge-magicness is p {divides} q(q+1). The edge magic index of a graph G is the least positive integer k such that the k-fold of G is edge-magic. In this paper, we prove that for any multigraph G with n vertices, n - 1 edges having no loops and no isolated vertices, the k-fold of G is edge-magic if n and k satisfy a necessary condition for edge-magicness and n is odd. For n even we also have some results on full m-ary trees and spider graphs. Some counterexamples of the edge-magic indices of trees conjecture are given.