A Complete Characterization of Magic Constants Arising from Distance Magic Graphs

Ravindra Pawar1, Tarkeshwar Singh1, Himadri Mukherjee1, Jay Bagga2
1Department of Mathematics, BITS Pilani K K Birla Goa Campus, Goa, India
2Department of Computer Science, Ball State University, Indiana, USA

Abstract

A positive integer \(k\) is called a magic constant if there is a graph \(G\) along with a bijective function \(f\) from \(V(G)\) to the first \(|V(G)|\) natural numbers such that the weight of the vertex \(w(v) = \sum_{uv \in E} f(u) = k\) for all \(v \in V\). It is known that all odd positive integers greater than or equal to \(3\) and the integer powers of \(2\), \(2^{t}\), \(t \geq 6\), are magic constants. In this paper, we characterize all positive integers that are magic constants and generate all distance magic graphs, up to isomorphism, of order up to \(10\).

Keywords: Magic constant, Distance magic graph, Backtracking Algorithm