Bounds on the Edge Magic Number for Complete Graphs

Abstract

An edge-magic total labeling of a graph $G=(V,E)$ is an assignment of integers $1,2,\dots ,|V|+|E|$ to the vertices and edges of the graph so that the sum of the labels of any edge $uv$ and the labels on vertices $u$ and $v$ is constant. It is known that the class of complete graphs on $n$ vertices, $K_n$, are not edge magic for any n ≥ 7. The edge magic number $M_E(K_n)$ is defined to be the minimum number t of isolated vertices such that $K_n\cup t{K}_1$, is edge magic. In this paper we show that, for n ≥ 10, $M_E(K_n)\le f_{n+1}+57–\frac{n^2+n}{2}where\text{(}{f}_i$ is the $i^{th}$ Fibonacci number. With the aid of a computer, we also show that $M_E(K_7)=4,M_E(K_8)=10$, and $M_E(K_9)=19$, answering several questions posed by W. D. Wallis.