The jumping knight and other (super) edge-magic constructions

Abstract

Let G be a graph of order p and size q with loops allowed. A bijective function f:V(G)∪E(G)→{i}p+qi=1 is an edge-magic labeling of G if the sum f(u)+f(uv)+f(v)=k is independent of the choice of the edge uv. The constant k is called either the valence, the magic weight or the magic sum of the labeling f. If a graph admits an edge-magic labeling, then it is called an edge-magic graph. Furthermore, if the function f meets the extra condition that f(V(G))={i}pi=1 then f is called a super edge-magic labeling and G is called a super edge-magic graph. A digraph D admits a labeling, namely l, if its underlying graph, und(D) admits l. In this paper, we introduce a new construction of super edge-magic labelings which are related to the classical jump of the knight on the chess game. We also use super edge-magic labelings of digraphs together with a generalization of the Kronecker product to get edge-magic labelings of some families of graphs.

The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.