A Complete Characterization of all Magic Constants Arising from Distance Magic Graphs

Ravindra Pawar [email protected] Tarkeshwar Singh [email protected] Himadri Mukherjee [email protected] Jay Bagga [email protected] Department 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 first $|V(G)|$ natural numbers such that the weight of the vertex $w(v)=\sum_{uv\in E}f(v)=k$ for all $v\in V$ . It is known that all odd positive integers greater equal $3$ and the integer powers of $2$ , $2^{t}$ , $t\geq 6$ are magic constants. In this paper we characterise all positive integers which are magic constants.

Keywords: Magic constant, Distance magic graph, Algorithm.
AMS Subject Classification 2021: 05C 78.

1 Introduction

Throughout this article, we will assume that $G=(V,E)$ denotes the finite simple graph with $V$ denoting the set of vertices and $E$ the set of edges. For a vertex, $u$ , its neighborhood is given by $N(u)=\{v\in V:uv\in E\}$ . A positive integer $k$ is called a magic constant if there is a graph $G$ along with a bijective function $f:V(G)\rightarrow\{1,2,\dots,|V(G)|\}$ such that the weight of the vertex $w(v)=\sum_{uv\in E}f(v)$ , remains constant and equal to $k$ for all $v\in V$ . Such labeling $f$ is called distance magic labeling. A graph equipped with distance magic labeling is known as a distance magic graph (for more details, see [1], [4]). We refer to West [13] for graph-theoretic terminology and notation not covered here.

Regardless of how the vertices are labeled, the magic constant remains invariant, as previously established [2, 10] i.e., it is independent of the distance magic labeling. At the International Workshop on Graph Labeling (IWOGL-2010), Arumugam [1] raised the question to characterise the set of positive integers, which are magic constants. Since then, this problem has captured the attention of researchers. The integers $1,2,4,6,8,12$ do not belong to the set of magic constants. On the other hand, all odd integers $\geq 3$ and all integers of the form $2^{t}~{}(t\geq 6)$ are confirmed members of the set of magic constants (see, [7], [8]). A previous study in [14] identified a graph with $8$ vertices that possesses a magic constant of $24$ . However, characterising the set of integers, which are magic constants, is an ongoing problem in distance magic graphs. We have shown that positive integers of the form $4t+2$ for $t\geq 3$ and of the form $4t+4$ for $t\geq 8$ are magic constants. Hence, the remaining numbers are $16,20,28$ , and $32$ .

Bertault et al. [3] introduced a heuristic algorithm to identify various classes of labelings. Building on this, Fuad et al. [14] refined the algorithm, achieving the construction of all distance magic graphs up to isomorphism for orders up to $9$ . This is the well-known algorithm available for constructing distance magic graphs. However, from a computational point of view, this algorithm has limitations. It relies on a collection of all non-isomorphic graphs as input, a formidable task that poses challenges, particularly for higher-order graphs. Generating all non-isomorphic graphs of substantial sizes remains computationally demanding, thereby affecting the practicality of the algorithm.

In this paper, we completely solve the characterization problem of magic constants. We prove this result by providing constructions of distance magic graphs to obtain specific magic constants.

We have devised an algorithm to check if there is a distance magic graph for a given number of vertices $n$ and a specific magic constant $k$ . We have implemented this algorithm to construct magic graphs for $k=20,28$ , and $32$ . Our search for $k=16$ shows that no graph admits the magic constant $16$ . Using this algorithm, we have generated all distance magic graphs up to isomorphism of order up to $12$ . This enhances the existing collection of distance magic graphs [14].

This algorithm serves as a practical tool for researchers and enthusiasts in the field of distance magic graphs. Addressing the general challenge of characterizing all graphs possessing distance magic labelings using algorithms presents a computational hurdle. This is mainly due to the impracticality of generating all non-isomorphic graphs since this becomes increasingly unfeasible as the graph order grows. Consequently, the algorithms devised for characterisation problems often encounter limitations or become computationally intensive when dealing with graphs of larger vertices.

It is believed that for a given $n$ , only a small subset of the set of all graphs of order $n$ possess the distance magic property. Consequently, a different approach is required rather than providing a collection of non-isomorphic graphs as input and subsequently characterizing them for the distance magic property. Instead, the focus shifts towards developing algorithms capable of dynamically constructing all distance magic graphs on $n$ vertices. By adopting this strategy, we can bypass the challenge of generating all non-isomorphic graphs. We have successfully implemented this approach.

2 Main Results

The magic constant of regular distance magic graphs can be easily calculated, as shown in the following theorem.

Theorem 2.1.

[6, 9, 11, 12] If $G$ is an $r$ -regular distance magic graph on $n$ vertices with magic constant $k$ , then $k=\frac{r(n+1)}{2}$ .

It is known that each positive integer of the form $4t+1$ is a magic constant of a graph union of $t$ copies of a $4$ -cycle $tC_{4}$ as stated in the following theorem.

Theorem 2.2.

[6] A graph $G$ of order $n$ is a distance magic graph with magic constant $k=n+1$ if and only if $G=tC_{4}$ , $t\geq 1$ .

Figure 1 shows the distance magic labeling of $3C_{4}$ with the magic constant $13$ .

Figure 1: A distance magic labeling of

3C_{4}

The following result shows that each positive integer of the form $4t+3$ is a magic constant of a graph $P_{3}\cup tC_{4}$ .

Theorem 2.3.

[6] Let $G$ be a distance magic graph with magic constant $k$ . Then, the following are equivalent.

1.

$k=n$ .
2.

$\delta(G)=1$ .
3.

Either $G$ is isomorphic to $P_{3}$ or $G$ contains exactly one copy of $P_{3}$ and all other components are isomorphic to $C_{4}$ .

Figure 2 shows the distance magic labeling of $P_{3}\cup 2C_{4}$ with magic constant $11$ .

Figure 2: A distance magic labeling of

P_{3}\cup 2C_{4}

From Theorem 2.2 and 2.3, we conclude that all odd positive integers $\geq 3$ are magic constants. This also answers the question: does $p^{t},t\geq 1$ belong to the set of magic constants, where $p$ is odd prime? (see [7]). As a special case of odd magic constants, we have found a direct construction for graphs with magic constant $p^{t}$ , where $p$ is an odd prime. We describe that next.

Proposition 2.4.

Given an odd prime $p$ , $p^{t}$ is a magic constant for all $t\geq 1$ .

Proof.

Let $p$ be an odd prime. Then $p$ is of one of the following forms.

Case i. $p\equiv 1(\bmod\ 4)$ .
Then $p^{t}\equiv 1(\bmod\ 4)$ , for all $t\geq 1$ and magic constant $p^{t}$ can be constructed by using $\frac{p^{t}-1}{4}$ copies of $C_{4}$ as given in Theorem 2.2.

Case ii. $p\equiv-1(\bmod\ 4)$ .
Then $p^{t}\equiv 1(\bmod\ 4)$ when $t$ is even and $p^{t}\equiv-1(\bmod\ 4)$ when $t$ is odd. When $t$ is even, we follow the argument as in case i above. Suppose $t$ is odd. If $t=1$ , we take $G=P_{3}\cup\lambda C_{4}$ , where $\lambda=\frac{p-3}{4}$ . Hence, by the Theorem 2.3, $k=p$ .

Now, suppose $t\geq 3$ . Consider a $p$ -regular graph $G$ on $n_{1}=\frac{p^{t-1}-1}{2}$ vertices. Then $G[\overline{K}_{2}]$ is a $2p$ -regular graph on $n=2n_{1}=p^{t-1}-1$ vertices. Therefore by Theorem 2.1, $k=\frac{2p((p^{t-1}-1)+1)}{2}=p^{t}$ as required. ∎

Now, we explore the case of the even positive integers, which are magic constant.
When $H$ is an arbitrary graph with vertices $x_{1},x_{2}\dots,x_{n}$ , and $G$ is any graph with $t$ vertices, then by $H[G]$ we denote the graph, which arises from $H$ by replacing each vertex $x_{i}$ by a copy of the graph $G$ with vertex set $X_{i}=\{x_{i_{1}},\dots,x_{i_{t}}\}$ , and each edge $x_{i}x_{j}$ by the edges of the complete bipartite graph $K_{t,t}$ with bipartition $X_{i},X_{j}$ . The graph $H[G]$ is then called lexicographic product or the composition of $H$ and $G$ .

Theorem 2.5.

[5, 9] If $G$ is an $r$ -regular graph, then $G[\overline{K}_{t}]$ is distance magic for any even $t$ .

In [9], the authors proved that for an $r$ -regular graph $G$ on $n$ vertices, the magic constant of $G[\overline{K}_{t}]$ is $k=rt(2nt+1)$ . With $r=2$ and $k=1$ , we obtain $k=4n+2$ . This gives the proof of the following theorem.

Theorem 2.6.

For all $t\geq 3$ , $4t+2$ is a magic constant.

In [8], the authors proved that there exists a $4$ -regular distance magic graph $G=(V,E)$ of odd order if and only if $|V|\geq 17$ . Now, we use this result to prove the existence of even magic constants of the form $4t+4$ , $t\geq 8$ .

Theorem 2.7.

For all $t\geq 8$ , $4t+4$ is a magic constant.

Proof.

Let $G$ be a $4$ -regular distance magic graph of odd order. Then, $|V(G)|\geq 17$ . By Theorem 2.1, the magic constant $k$ of such a graph $G$ is given by $k=\frac{4(|V|+1)}{2}=2|V|+2$ . If we write $|V|=2t+1$ , where $t\geq 8$ , then $k=4t+4$ . This proves the theorem. ∎

We already know that the integers $1,2,4,6,8$ and $12$ are not magic constants [7], while $10$ and $24$ are magic constants (see, [7], [14]). Theorems 2.6 and 2.7 provide further insights into the nature of the set of magic constants. Theorem 2.6 reveals that all positive integers congruent to $2(\bmod\ 4)$ , with the exceptions of $2$ and $6$ , are the members of the set of magic constants. Meanwhile, Theorem 2.7 establishes that all positive integers greater than or equal to $36$ and congruent to $0(\bmod\ 4)$ are also in the set of magic constants.

As a result, the only remaining even positive integers requiring examination as magic constants are $16,20,28$ , and $32$ . We device an algorithmic approach to determine whether these integers qualify as magic constants of some graphs. Thus we have a complete characterisation of all magic constants (see Theorem 4.1).

3 An algorithm for constructing magic graphs and computing magic constants

Given positive integers $n$ and $k$ , our algorithm checks if there exists a graph with vertex set $\{1,2,\dots,n\}$ and a magic constant $k$ . We denote any such graphs as $G(n,k)$ . Without loss of generality, we may assume that each vertex $i$ is labeled as $i$ for $1\leq i\leq n$ . The algorithm returns the first successful search if such a magic graph exists.

Let $S$ be the set of all subsets of the set $\{1,2,\dots,n\}$ with the sum of its elements equal to $k$ . For each $1\leq i\leq n$ , let $NS(i)=\{T\in S:i\not\in T\}$ . Note that if there exists a distance magic graph $G(n,k)$ , then the neighborhood of a vertex $i$ , $N(i)$ , must be a member of $NS(i)$ . Next, fix a neighborhood of a vertex $n$ , i.e., an element of $NS(n)$ , and construct a tree rooted at $N(n)$ in the following manner. Add all elements in $NS(n-1)$ as children to $N(n)$ . This is level $1$ . Add elements of $NS(n-2)$ as children to each node in level $1$ . This is level $2$ . Continue till we add all elements in $NS(1)$ to each node in level $n-1$ . Note that in level $i$ , each node of this tree $T(n,k)$ is a possible candidate for a $N(i)$ . Each branch of this tree $T(n,k)$ gives an adjacency list for the vertices $1,2,\dots,n$ . These lists may or may not correspond to a graph. Whenever adjacency lists corresponding to a branch give a graph, we call such a branch a successful branch.

The algorithm consists of the following four steps:

3.1 Algorithm

Step 1.

Generate all subsets of the set $\{1,2,\dots,n\}$ that have the sum of its elements equal to $k$ .
Step 2.

For each $1\leq i\leq n$ , construct $NS(i)$ .
Step 3.

Construct a rooted tree $T(n,k)$ with a root as a fixed element of $NS(n)$ .
Step 4

For a tree $T(n,k)$ obtained in Step ( $3$ ), find a successful branch. Repeat Steps ( $3$ ) and ( $4$ ) for each element of $NS(n)$ until we find a successful branch, or we run out of elements in $NS(n)$ .

The approach described above is a brute force in some sense. For example, for the case $n=30$ , $k=32$ , there are more than $10^{76}$ branches to explore. We merge Step $(3)$ and Step $(4)$ to say Step ( $3^{\prime}$ ) to optimise the search space as:

Step $3^{\prime}$

We explore the branches of $T(n,k)$ as discussed in Step $(3)$ and Step $(4)$ with the following condition. Let the tree be constructed till level $i(2\leq i\leq n-1)$ and $NS(i)=\{s_{1},s_{2},\dots,s_{t_{i}}\}$ , $NS(i+1)=\{r_{1},r_{2},\dots,r_{t_{h}}\}$ . Next, while adding children $r_{b}$ to any of the $s_{a}$ we will check

$i+1\text{ is in any of it's parents }s_{a}\text{ if and only if }i\in r_{b}.$ (1)

Also, at any moment,

$\text{neighborhood sum of any vertex does not exceed }k.$ (2)

Step ( $3^{\prime}$ ) ensures symmetry, meaning that $u$ is adjacent to $v$ if and only if $v$ is adjacent to $u$ . If the condition stated in 1 or 2 is not met at any step, we avoid adding the corresponding node, preventing further growth of the tree below that node. This reduction strategy significantly reduces the size of the tree $T(n,k)$ , leading to an exponential reduction in the search space.

3.2 Proof of correctness

It is sufficient to prove that every $G(n,k)$ graph corresponds to a (successful) branch of some $T(n,k)$ and each successful branch of each $T(n,k)$ corresponds to some graph $G(n,k)$ . It is easy to observe that if $T(n,k)$ has a successful branch, then nodes on that branch constitute a graph $G(n,k)$ .

Conversely, suppose there is a graph $G(n,k)$ . Consider a tree $T(n,k)$ rooted at $N(n)$ . There is a one-to-one correspondence between branches of $T(n,k)$ and the elements of the cartesian product $N(n)\times NS(n-1)\times\dots\times NS(1)$ . The neighborhood of each vertex $i$ , $N(i)$ , is a member of $NS(i)$ . Hence, $N(n)\times N(n-1)\times\dots\times N(1)$ is an element of the cartesian product $N(n)\times NS(n-1)\times\dots\times NS(1)$ . Thus, it corresponds to some branch of $T(n,k)$ .

3.3 Illustration

Let us illustrate these steps with an example. Let $n=7$ and $k=7$ . We know that there is only one graph $P_{3}\cup C_{4}$ up to isomorphism on $7$ vertices admitting magic constant $7$ [14]. All subsets of the set $\{1,2,\dots,7\}$ having sum $7$ are:

\bigr{[}[7],\;[6,1],\;[5,2],\;[4,3],\;[4,2,1]\bigr{]}.

We have listed all the subsets as a list of lists for the proper indexing purpose in the pseudo-code. This completes Step $1$ . Next, we generate all possible neighborhood sets for each vertex as suggested in Step $2$ .

	$\displaystyle NS(1)=\bigr{[}[7],\;[5,2],\;[4,3]\bigr{]}$
	$\displaystyle NS(2)=\bigr{[}[7],\;[6,1]\;[4,3]\bigr{]}$
	$\displaystyle NS(3)=\bigr{[}[7],\;[6,1],\;[5,2],\;[4,2,1]\bigr{]}$
	$\displaystyle NS(4)=\bigr{[}[7],\;[6,1],\;[5,2]\bigr{]}$
	$\displaystyle NS(5)=\bigr{[}[7],\;[6,1],\;[4,3]\;[4,2,1]\bigr{]}$
	$\displaystyle NS(6)=\bigr{[}[7],\;[5,2],\;[4,3],\;[4,2,1]\bigr{]}$
	$\displaystyle NS(7)=\bigr{[}[6,1],\;[5,2],\;[4,3],\;[4,2,1]\bigr{]}$

Now we construct a tree $T(7,7)$ rooted at the node $[6,1]$ from $NS(7)$ . This makes $N(7)=[6,1]$ . Add all the elements of the set $NS(6)$ as children to the root node as shown in Figure 3. The set of possible candidates for $N(6)$ is

NS(6)=\bigr{[}[7],\;[5,2],\;[4,3],\;[4,2,1]\bigr{]}

We have chosen $NS(7)=[6,1]$ , to maintain symmetry we must have $7\in N(6)$ . The only such element in $NS(6)$ is $[7]$ . Hence, we discard all other nodes in the level $1$ , and the tree won’t grow further below those nodes. Now we go to level $2$ . The set of possible candidates for $N(5)$ is

NS(5)=\bigr{[}[7],\;[6,1],\;[4,3]\;[4,2,1]\bigr{]}

So far we have $N(7)=[6,1]$ and $N(6)=[7]$ . Since $5\not\in N(6)\cup N(7)$ , $6,7\not\in N(5)$ maintaining the condition given in (1) of Step $3^{\prime}$ . Then the only choices for $N(5)$ are $[4,3]$ and $[4,2,1]$ . Without loss of generality consider $N(5)=[4,3]$ . Now we go to level $3$ . The set of possible candidates for $N(4)$ is

NS(4)=\bigr{[}[7],\;[6,1],\;[5,2]\bigr{]}

So far we have $N(7)=[6,1]$ , $N(6)=[7]$ and $N(5)=[4,3]$ . Here $4\not\in N(6)\cup N(7)$ hence $6,7\not\in N(4)$ but $4\in N(5)$ hence $N(4)$ must contain $5$ . The only choice for $N(4)$ is $[5,2]$ . We continue in a similar way, and lastly, we add pendants $[7]$ , $[5,2]$ , and $[4,3]$ from the set $NS(1)$ . For $N(1)$ we discard the nodes $[5,2]$ and $[4,3]$ because $1\not\in N(j)$ for any $j=2,3,4,5$ and we must $N(1)$ must have $7$ since $1\in N(7)$ hence maintaining symmetry condition as given in (1) of Step $3^{\prime}$ .

Figure 3: A tree

T(n,k)

rooted at

[6,1]

with a successful branch.

In Figure 3, we have illustrated a case of a successful branch (colored blue).

Now let us consider where we select the node $[4,2,1]$ instead of $[4,3]$ at level $2$ . In this case so far we have $N(7)=[6,1]$ , $N(6)=[7]$ and $N(5)=[4,2,1]$ . Then we go to level $3$ . The set of possible candidates for $N(4)$ is:

NS(4)=\bigr{[}[7],\;[6,1],\;[5,2]\bigr{]}

Since $4\not\in N(6)\cup N(7)$ but $4\in N(5)$ , we must have $6,7\not\in N(4)$ but $5\in N(4)$ . The only such possibility is $[5,2]$ . We go to the next level $4$ . The set of possible candidates for $N(3)$ is:

NS(3)=\bigr{[}[7],\;[6,1],\;[5,2],\;[4,2,1]\bigr{]}

Since $3\not\in N(j)$ for any $j=4,5,6,7$ and each list in $NS(3)$ contains at least one of the numbers $4,5,6,7$ , in order to maintain the symmetry $N(3)$ has no choices and we discard this branch. This discarded branch is shown in red color in Figure 3.

Figure 4:

G(11,55)

3.4 Graphs output with our algorithm

For a distance magic graph $G$ on $n$ vertices with distance magic labeling $f$ and magic constant $k$ , it is easily seen that $\sum_{v\in V}deg(v)f(v)=nk$ [12]. For any vertex $v$ , $1=\delta(G)\leq deg(v)\leq\Delta(G)=n-1$ . Hence, we have an upper bound $k\leq\frac{n^{2}-1}{2}$ . This bound is sharp (Figure 4 shows an example). Also, by definition of the distance magic graph, $k$ cannot be less than $n$ . Hence, we have $n\leq k\leq\frac{n^{2}-1}{2}$ and both the bounds are sharp. To check whether a given positive integer $k$ is a magic constant, we need to run the algorithm for each pair $(n,k)$ , where $1\leq n\leq k$ . Let $\alpha$ be the smallest positive integer such that $\frac{\alpha(\alpha+1)}{2}\leq k$ . Hence, running the algorithm for the pairs $(n,k)$ , where $\alpha\leq n\leq k$ is sufficient. For example for $k=16$ , the possibilities for $n$ are $6,7,\dots,16$ . Further, we can omit a few values in some cases, as mentioned in (Chapter 2, [7]).
Our algorithm explores the possibility of $k=16$ being the magic constant for the graphs on a possible number of vertices $n$ . However, findings show that no graph admits the magic constant $16$ . On the other hand, multiple graphs admit $20,28,32$ as magic constants. As a representative example, we list one of the such graphs in Figure 5. It’s not practical to list all the non-isomorphic distance magic graphs of order up to $12$ due to their abundance (more than a thousand in number, see Table 1), we will list them of order up to $10$ . Also, the collection of distance magic graphs of order up to $9$ , generated using our algorithm is the same as the one given in [14] except for graphs of order $8$ . Hence, we list the distance magic graphs of order $8$ and $10$ only (see figures 6, 7).

number of vertices: $n$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
number of non-isomorphic distance magic graphs	$1$	$1$	$1$	$1$	$3$	$6$	$5$	$5$	$74$	$1160$

Table 1: Number of non-isomorphic distance magic graphs of order up to

12

3.5 Pseudo-code

For a given value of $n$ and $k$ , the Step $1$ of the algorithm involves the generation of all subsets of a set $\{1,2,\cdots,n\}$ with sum $k$ . The algorithm may try all subsets of the given set in worst case. As a result, the time complexity of the above algorithm is exponential. However, our primary goal is to efficiently generate distance magic graphs only for specific values of $n$ and $k$ , so we do not place a strong emphasis on the time complexity of this algorithm.

We provide the complete pseudo-code for the algorithm.

Algorithm 1 Distance magic graph generator

1:• To generate

k

-sum subsets

2:function getSubset(

A,k,n,\text{ans},\text{List}

)

A\leftarrow\text{list of integers from 1 to }n

\text{ans}\leftarrow\text{empty list}

\text{List}\leftarrow\text{empty list}

6: if

k=0

then

ans1\leftarrow ans

8: List.append(ans1)

9: return

10: if

k\neq 0

and

n=\text{length of }A-1

then

11: return

12: if

k-A[n]\geq 0

then

13: ans.append

(A[n])

14: getSubset

(A,k-A[n],n-1,\text{ans},\text{List})

\triangleright

include the element

15: ans.pop()

16: getSubset

(A,k,n-1,ans,List)

\triangleright

do not include the element

17:• To generate neighborhood sets

NS

18:function generate_neighbors(

n,k

)

19: getSubset(A,

k

n-1

, ans, List)

20:

\text{neighborhoods}\leftarrow\text{empty list}

21: for

i\leftarrow 1

n

22:

N_{i}\leftarrow\text{empty list}

23: for each subset in List do

24: if

i\notin\text{subset}

then

25:

N_{i}\leftarrow\text{append subset to }N_{i}

26:

\text{append }N_{i}\text{ to neighborhoods}

27: return neighborhoods

28:

\text{adj}\leftarrow\text{list of empty lists of size }n+1

29:

\text{sum\_list}\leftarrow\text{list of }n+1\text{ elements initialized to }0

30:

\text{\text{cnt\_depth}}\leftarrow 0

31:

\text{successful}\leftarrow\text{list containing a single element }0

32:

N\leftarrow\text{generate\_neighbors}(n,k)

33:N.insert(0, [ ])

34:function is_symmetric(adj, n, depth)

\triangleright

Checks the condition in (1) in Step

3^{\prime}

35: for

i\leftarrow n

\text{depth}-1

36: for each neighbor in adj[i] do

37: if

\text{neighbor}\leq\text{depth}

then

38: continue

39: if

i\notin\text{adj[neighbor]}

then

40: return False

(Continued)

1:function check(adj_list, sum_list)

\triangleright

Checks the condition given in (2) in Step

3^{\prime}

\text{done}\leftarrow 1

3: for

i\leftarrow 1\text{ to length of adj\_list}

4: if

\text{sum\_list}[i]\neq k

then

\text{done}\leftarrow 0

6: break

7:• To construct a tree

T(n,k)

and explore the successful branch

8:function explorer(N, adj, depth, breadth, sum_list, successful)

\text{adj}[\text{depth}]\leftarrow\text{N}[\text{depth}][breadth]

\triangleright

Fixes first element of

NS(n)

as a root of

T(n,k)

10: if depth = 1 then

11: for

i\leftarrow 1

\text{length of adj}[\text{depth}]

12:

\text{sum\_list}[\text{adj}[\text{depth}][i]]\leftarrow\text{sum\_list}[\text{adj}[\text{depth}][i]]+\text{depth}

13: if check(adj, sum_list) and is_symmetric(adj, n, depth) then

14:

\text{successful}[0]\leftarrow\text{successful}[0]+1

15: for

i\leftarrow 1

\text{length of adj}[\text{depth}]

16:

\text{sum\_list}[\text{adj}[\text{depth}][i]]\leftarrow\text{sum\_list}[\text{adj}[\text{depth}][i]]-\text{depth}

17: Print the adjacency list of the graph

18: return True

19: for

i\leftarrow 1

\text{length of adj}[\text{depth}]

20:

\text{sum\_list}[\text{adj}[\text{depth}][i]]\leftarrow\text{sum\_list}[\text{adj}[\text{depth}][i]]-\text{\text{depth}}

21: return False

22:

\text{flag}\leftarrow\textbf{is\_symmetric}(\text{adj, n, depth})

23: for

i\leftarrow 1

\text{length of adj}[depth]

24:

\text{sum\_list}[\text{adj}[\text{depth}][i]]\leftarrow\text{sum\_list}[\text{adj}[\text{depth}][i]]+\text{depth}

25: if

\text{sum\_list}[\text{adj}[\text{depth}][i]]>k

then

26:

\text{flag}\leftarrow 0

27: if

\text{flag}=1

then

28: for

i\leftarrow 1

\text{length of N}[\text{depth}-1]

29: if explorer

(N,\text{adj},\text{\text{depth}}-1,i,\text{sum\_list},\text{successful})

then

30: return True

31: for

i\leftarrow 1

\text{length of adj}[\text{depth}]

32:

\text{sum\_list}[\text{adj}[\text{depth}][i]]\leftarrow\text{sum\_list}[\text{adj}[\text{depth}][i]]-\text{depth}

33:

\text{adj}[\text{depth}]\leftarrow\text{empty list}

34: return False

35:for

i\leftarrow 1

\text{length of N}[n]

\triangleright

to construct

T(n,k)

rooted at each element in

NS(n)

36: explorer

(N,\text{adj},n,i,\text{sum\_list},\text{successful})

4 Conclusions

With the results known earlier, and those proved in this paper, the magic constants are now completely characterized, as shown in the following theorem.

Theorem 4.1.

All positive integers except $1,2,4,6,8,12$ , and $16$ are magic constants.

Not all magic constants arise from connected graphs. Also, for some integers, for example, $n=k=7$ , there is a unique distance magic graph $G(n,k)$ . This leads naturally to the following questions.

1.

Which magic constants are realised by connected distance magic graphs?
2.

For which pairs $(n,k)$ , there is unique distance magic graph on $n$ vertices with magic constant $k$ ?

Acknowledgement: The authors are grateful to Atharv Karandikar and Satyaprasad for their invaluable assistance in implementing the algorithm.

References

[1] S. Arumugam, D. Froncek, and N. Kamatchi. Distance magic graphs—a survey. J. Indones. Math. Soc., (Special edition):11–26, 2011.
[2] S. Arumugam, N. Kamatchi, and G. R. Vijayakumar. On the uniqueness of $D$ -vertex magic constant. Discuss. Math. Graph Theory, 34(2):279–286, 2014.
[3] Bertault François, F. Raquel, M. Miller, P. Helmut, and V. Ehsan. A heuristic for magic and antimagic graph labellings. In Proc. VII Spanish Congress on Metaheuristics and Evolutive and Bioinspired Algorithms 2010, pages 677–684, 2010.
[4] J. A. Gallian. A dynamic survey of graph labeling (25th edition). Electron. J. Combin., 5:Dynamic Survey 6, 43, 2022.
[5] A. Godinho and T. Singh. Some distance magic graphs. AKCE Int. J. Graphs Comb., 15(1):1–6, 2018.
[6] M. Jinnah. On ${\Sigma}$ -labelled graphs. In B.D. Acharya and S.M. Hedge, editors, Technical Proceedings of Group Discussion on Graph Labeling Problems, pages 71–77. NITK Surathkal, 1999.
[7] N. Kamatchi. Distance Magic and Distance Antimagic Labelings of Graphs. Phd thesis, Kalasalingam Academy of Research and Education, Krishnankoil, Srivilliputhur, Tamil Nadu, June 2012.
[8] P. Kovář, D. Fronček, and T. Kovářová. A note on 4-regular distance magic graphs. Australas. J. Combin., 54:127–132, 2012.
[9] M. Miller, C. Rodger, and R. Simanjuntak. Distance magic labelings of graphs. Australas. J. Combin., 28:305–315, 2003.
[10] A. O’Neal and P. J. Slater. Uniqueness of vertex magic constants. SIAM J. Discrete Math., 27(2):708–716, 2013.
[11] S.B. Rao, T. Singh, and V. Parmeswaran. Some sigma labelled graphs i. In S. Arumugam, B.D. Acharya, and S.B. Rao, editors, Graphs, Combinatorics, Algorithms and Applications, pages 135–140. Narosa Publishing House, New Delhi, 2008.
[12] V. Vilfred. $\Sigma$ -Labelled Graphs and Circulant Graphs. Phd thesis, University of Kerala, Trivandrum, Kerala, India, 1994.
[13] D. B. West. Introduction to Graph Theory. Prentice Hall, 2nd edition, September 2000.
[14] F. Yasin and R. Simanjuntak. A heuristic for distance magic labeling. Procedia Computer Science, 74:100–104, 2015. “The 2nd International Conference of Graph Theory and Information Security”.