Electronic Journal of Graph Theory and Applications

Orientable \(\mathbb{Z}_n\)-distance magic labeling of the Cartesian product of many cycles

Bryan Freyberg^a, Melissa Keranen^b

bryan.freyberg@smsu.edu, msjukuri@mtu.edu

The following generalization of distance magic graphs was introduced in [2]. A <u>directed</u> \(\mathbb{Z}_n\)distance magic labeling of an oriented graph \(\overrightarrow{G} = (V, A)\) of order n is a bijection \(\overrightarrow{\ell} : V \to \mathbb{Z}_n\)with the property that there is a \(\mu \in \mathbb{Z}_n\) (called the magic constant) such that

\[w(x) = \sum_{y \in N_G^+(x)} \overrightarrow{\ell}(y) - \sum_{y \in N_G^-(x)} \overrightarrow{\ell}(y) = \mu \text{ for every } x \in V(G).\]

If for a graph G there exists an orientation \(\overrightarrow{G}\) such that there is a directed \(\mathbb{Z}_n\)-distance magic labeling \(\overrightarrow{\ell}\) for \(\overrightarrow{G}\), we say that G is orientable \(\mathbb{Z}_n\)-distance magic and the directed \(\mathbb{Z}_n\)-distance magic labeling \(\overrightarrow{\ell}\) we call an orientable \(\mathbb{Z}_n\)-distance magic labeling. In this paper, we find orientable \(\mathbb{Z}_n\)-distance magic labelings of the Cartesian product of cycles. In addition, we show that even-ordered hypercubes are orientable \(\mathbb{Z}_n\)-distance magic.

Keywords: distance magic graph, directed distance magic labeling, orientable \(\mathbb{Z}_n\)-distance magic labeling

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2017.5.2.11

Received: 20 September 2016, Revised: 30 July 2017, Accepted: 8 September 2017.

^&lt;sup>a</sup>Department of Mathematics and Computer Science, Southwest Minnesota State University, Marshall, MN 56258

^&lt;sup>b</sup>Department of Mathematical Sciences, Michigan Technological University, Houghton, MI 49931

1. Introduction

A distance magic labeling of an undirected graph G of order n is a bijection \(l:V(G)\to \{1,2,...,n\}\) such that \(\sum_{y\in N(x)} l(y)\) is the same for every \(x\in V(G)\). For a comprehensive survey of distance magic labeling, we refer the reader to [1].

An orientable \(\mathbb{Z}_n\)-distance magic labeling of a graph, first introduced by Cichacz et al. in [2], is a generalization of distance magic labeling. Let G=(V,E) be an undirected graph on n vertices. Assigning a direction to the edges of G gives an oriented graph \(\overrightarrow{G}=(V,A)\). We will use the notation \(\overrightarrow{xy}\) to denote an edge directed from vertex x to vertex y. That is, the tail of the arc is x and the head is y. For a vertex x, the set of head endpoints adjacent to x is denoted by \(N^-(x)\), while the set of tail endpoints is denoted by \(N^+(x)\). A directed \(\mathbb{Z}_n\)-distance magic labeling of an oriented graph \(\overrightarrow{G}(V,A)\) of order n is a bijection \(\overrightarrow{\ell}:V\to\mathbb{Z}_n\) with the property that there is a \(\mu\in\mathbb{Z}_n\) (called the magic constant) such that

\[w(x) = \sum_{y \in N_G^+(x)} \overrightarrow{\ell}(y) - \sum_{y \in N_G^-(x)} \overrightarrow{\ell}(y) = \mu \text{ for every } x \in V(G).\]

If for a graph G there exists an orientation \(\overrightarrow{G}\) such that there is a directed \(\mathbb{Z}_n\)-distance magic labeling \(\overrightarrow{\ell}\) for \(\overrightarrow{G}\), we say that G is orientable \(\mathbb{Z}_n\)-distance magic and the directed distance magic labeling \(\ell\) we call an orientable \(\mathbb{Z}_n\)-distance magic labeling.

Throughout this paper we will use the notation [n] to represent the set \(\{0,1,...,n-1\}\) for a natural number n. Furthermore, for a given \(i \in [n]\) and any integer j, let i+j denote the smallest integer in [n] such that \(i+j \equiv i+j \pmod n\). For a set of integers S and a number a, let \(S+a=\{s+a:s\in S\}\).

Let \(C_n = \{x_0, x_1, ..., x_{n-1}, x_0\}\) denote a cycle of length n. For the sake of orienting the cycle, if the edges are oriented such that every arc has the form \(\overrightarrow{x_i x_{i+1}}\) for all \(i \in [n]\), then we say the cycle is oriented clockwise. On the other hand, if all the edges of the cycle are oriented such that every arc has the form \(\overrightarrow{x_i x_{i-1}}\) for all \(i \in [n]\), then we say the cycle is oriented counter-clockwise.

2. Cartesian product of two cycles

The Cartesian product \(G \square H\) is a graph with the vertex set \(V(G) \times V(H)\). Two vertices (g, h) and (g', h') are adjacent in \(G \square H\) if and only if g = g' and h is adjacent with h' in H, or h = h' and g is adjacent with g' in G. Hypercubes are interesting graphs which arise via the Cartesian product of cycles. The hypercube of order 2k, \(Q_{2k}\) is equivalent to the graph \(C_4 \square C_4 \square ... \square C_4\), where \(C_4\) appears k times in the product. This graph is 2k regular on \(4^k\) vertices. Labeling hypercubes has provided the motivation for the following theorems. Recall the following theorem proved in [2].

Theorem 2.1. ([2]) The Cartesian product of cycles, \(C_m \square C_n\) is orientable \(\mathbb{Z}_{mn}\)-distance magic for all \(m \geq 3\) and \(n \geq 3\).

The next theorem lays the groundwork for labeling hypercubes.

Theorem 2.2. For any \(p \ge 1\), and \(m \ge 3\), p disjoint copies of the graph \(C_m \square C_m\) is orientable \(\mathbb{Z}_{pm^2}\)-distance magic.

Proof. Let \(G \cong C_m \cong \{g_0, g_1, ..., g_{m-1}, g_0\} \cong \{h_0, h_1, ..., h_{m-1}, h_0\} \cong H\). Then orient each copy of \(G \square H\) as follows. Fix \(j \in [m]\). Then for all \(i \in [m]\), orient clockwise each cycle of the form \(\{(g_i, h_j), (g_{i+1}, h_j), ..., (g_{i-1}, h_j), (g_i, h_j)\}\). Similarly, fix \(i \in [m]\). Then for all \(j \in [m]\), orient clockwise each cycle of the form \(\{(g_i, h_j), (g_i, h_{j+1}), ..., (g_i, h_{j-1}), (g_i, h_j)\}\). Since the graph \(G \square H\) can be edge-decomposed into cycles of those two forms, we have oriented every edge in each copy of \(G \square H\). Now let \({}^k x_i^j\) denote the vertex \((g_i, h_j)\) of the \(k^{th}\) copy of \(G \square H\) for \(i, j \in [m]\), and \(k \in \{1, 2, ..., p\}\). Then, for each \(k \in \{1, 2, ..., p\}\), define \(l : V \to \mathbb{Z}_{pm^2}\) by

\[\vec{l}(^kx_i^j) = pmj + (k-1)m + \boldsymbol{i} - \boldsymbol{j},\]

where the arithmetic is done modulo \(pm^2\).

Expressing \(\vec{l}(^kx_i^j)\) in the following alternative way

\[\vec{l}(^kx_i^j) = \begin{cases} pmj + (k-1)m, & \text{for } i \equiv j \pmod{m} \\ pmj + (k-1)m + 1, & \text{for } i \equiv j+1 \pmod{m} \\ pmj + (k-1)m + 2, & \text{for } i \equiv j+2 \pmod{m} \\ \vdots & \vdots \\ pmj + (k-1)m + (m-1), & \text{for } i \equiv j-1 \pmod{m} \end{cases}\]

makes it easy to see that \(\vec{l}\) is clearly bijective. Then for any given k and for all \(i, j \in [m]\) we have \(N^+ \binom{k}{x_i^j} = \binom{k}{x_i^{j+1}}, \ kx_{i+1}^j\) and \(N^- \binom{k}{x_i^j} = \binom{k}{x_i^{j-1}}, \ kx_{i-1}^j\). Recalling that \(w(^kx_i^j) \in \mathbb{Z}_{pm^2}\), we have

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

so \(\vec{l}\) is an orientable \(\mathbb{Z}_{pm^2}\)-distance magic labeling. Hence, p copies of \(C_m \square C_m\) is orientable \(\mathbb{Z}_{pm^2}\)-distance magic.

3. Cartesian product of many cycles

Theorem 3.1. For any \(m \geq 3\), the Cartesian product \(C_m \square C_m \square ... \square C_m\) is orientable \(\mathbb{Z}_{m^n}\)-distance magic.

Proof. Let \(G_n\cong C_m\square C_m\square...\square C_m\), the Cartesian product of n \(C_m\)'s. Then for \(n\geq 2\) we may describe \(G_n\) recursively as \(G_n\cong G_{n-1}\square C_m\). We also have that, \(|V(G_n)|=m^n\), so the labeling will take place in \(\mathbb{Z}_{m^n}\). The proof is by induction. For n=1, we apply the labeling \(\left\{x_0^0,x_0^1,...,x_0^{m-1}\right\}\longmapsto \{0,1,...,m-1\}\) and orient the cycle clockwise. Clearly for \(j\in\{0,m-1\}, w(x_0^j)=2-m\equiv 2\pmod{m}\) and for 0< j< m-1, we have \(w(x_0^j)=2\equiv 2\pmod{m}\), so \(G_1\) is orientable distance magic. For n=2, Theorem 2.2 gives that \(G_2\) is orientable distance magic and using the nomenclature from Theorem 2.2, \(w(x_i^j)=(2-m)m\equiv 2m\pmod{m^2}\) for \(j\in\{0,m-1\}, i\in[m]\) and \(w(x_i^j)=2m\) for \(j\in\{0< j< m-1\}, i\in[m]\). Furthermore, for each fixed j, the labels of \(x_i^j\) belong to the set [m]+jm for both base cases. Now construct \(G_n\cong G_{n-1}\square C_m\) as follows. Let \(H_i\cong G_{n-1}\) for \(i\in[m]\). Furthermore, for a given i, let \(H_i^j\cong G_{n-2}\) for \(j\in[m]\). Let \(x_i^j\) denote an arbitrary vertex in the subgraph \(H_i^j\). Then for any integers a,b let \(x_{i+a}^{j+b}\) denote the corresponding vertex in the isomorphic subgraph \(H_i^j\). Using this terminology, we have \(N_{G_n}\left(x_i^j\right)=N_{G_{n-1}}(x_i^j)\cup \left\{x_{i+1}^j,x_{i-1}^j\right\}\). Let \(w_{H_i}(x_i^j)\) denote the weight (in \(\mathbb{Z}_m\)) induced on \(x_i^j\) by the subgraph \(H_i^j\). Now partition \(\mathbb{Z}_{m^{n-1}}=P_0\cup P_1\cup P_2\cup...\cup P_{m-1}\) so that \(P_j=[m^{n-2}]+jm^{n-2}\) for \(j\in[m]\).

Now assume \(G_{n-1}\) is orientable \(\mathbb{Z}_{m^{n-1}}\)-distance magic with labeling \(\vec{l'}: V(G_{n-1}) \to \mathbb{Z}_{m^{n-1}}\). Then in \(G_n\), apply \(\vec{l'}\) and its corresponding orientation to \(H_0 \cong G_{n-1}\). As in the base cases, we may assume that the labels of \(H_0^j\) belong to \(P_j\) for \(j \in [m]\) and

\[w_{H_0}(x_0^j) = \begin{cases} (2-m)m^{n-2}, j \in \{0, m-1\} \\ 2m^{n-2}, j \in \{1, 2, \dots m-2\} \end{cases}\]

Next, orient all the edges in each subgraph \(H_1, H_2, ..., H_{m-1}\) as in \(H_0\). Then the only edges left to orient in \(G_n\) are cycles of the type \(\left\{x_0^j, x_1^j, ..., x_{m-1}^j\right\}\) for fixed j. Orient each of these cycles clockwise. Now define \(\vec{l}: V(G_n) \to \mathbb{Z}_{m^n}\) as follows.

\[\vec{l}(x_i^j) = \begin{cases} \vec{l'}(x_0^j) + i(m-1)m^{n-2} + m^{n-1}, \ 0 \le j < i \\ \vec{l'}(x_0^j) + i(m-1)m^{n-2}, \ i \le j \le m-1 \end{cases}.\]

To show that \(\vec{l}\) is a bijection, it suffices to show that for each fixed \(i, \vec{l}: P_j \longmapsto P_{j-i} + im^{n-1}\) for all j, since for each fixed i, j - i runs through [m] as j runs through [m]. Since the labels of \(H_0^j\) belong to \(P_j\) for \(j \in [m]\), we have

\[\vec{l}: P_j \longmapsto \begin{cases} P_j + i(m-1)m^{n-2} + m^{n-1}, \ 0 \le j < i \\ P_j + i(m-1)m^{n-2}, \ i \le j \le m-1 \end{cases}\]

Now, if \(0 \le j < i\), we have

\[\begin{array}{lll} P_{j} & \mapsto & P_{j} + i(m-1)m^{n-2} + m^{n-1} \\ & = & [m^{n-2}] + jm^{n-2} + i(m-1)m^{n-2} + m^{n-1} \\ & = & [m^{n-2}] + (j-i)m^{n-2} + (i+1)m^{n-1} \\ & = & [m^{n-2}] + (j-i)m^{n-2} + mm^{n-2} + im^{n-1} \\ & = & [m^{n-2}] + (m+j-i)m^{n-2} + im^{n-1} \\ & = & P_{j-i} + im^{n-1}. \end{array}\]

While if \(i \le j \le m-1\), we have

\[P_{j} \mapsto P_{j} + i(m-1)m^{n-2}\] \[= [m^{n-2}] + jm^{n-2} + i(m-1)m^{n-2}\] \[= [m^{n-2}] + (j-i)m^{n-2} + im^{n-1}\] \[= P_{j-i} + im^{n-1}.\]

Therefore, it is clear that for each \(i \in [m]\), the label set used on \(H_i\) is \(i \cdot m^{n-1} + \{P_0 \cup P_1 \cup ... \cup P_{m-1}\} = \mathbb{Z}_{m^{n-1}} + im^{n-1}\), so we see that \(\overrightarrow{l}: V(G_n) \to \mathbb{Z}_{m^n}\) is bijective. This completes the labeling and orientation of \(G_n\).

Observe that \(\vec{l}(x_i^j) \equiv \vec{l}'(x_0^j) \pmod{m^{n-2}}\). Therefore, \(w_{H_i^j}(x_i^j) = w_{H_0^j}(x_0^j)\) in \(\mathbb{Z}_{m^n}\). Then we have,

\[w_{H_{i}}(x_{i}^{j}) = w_{H_{i}^{j}}(x_{i}^{j}) + \vec{l}(x_{i}^{j+1}) - \vec{l}(x_{i}^{j-1})\]
= \(w_{H_{0}^{j}}(x_{0}^{j}) + \vec{l}(x_{i}^{j+1}) - \vec{l}(x_{i}^{j-1}).\)

But,

\[w_{H_0^j}(x_0^j) = w_{H_0}(x_0^j) - [\vec{l'}(x_0^{j+1}) - \vec{l'}(x_0^{j-1})].\]

Therefore,

\[w_{H_{i}}(x_{i}^{j}) = w_{H_{0}}(x_{0}^{j}) - \vec{l'}(x_{0}^{j+1}) + \vec{l'}(x_{0}^{j-1}) + \vec{l}(x_{i}^{j+1}) - \vec{l}(x_{i}^{j-1})\] \[= w_{H_{0}}(x_{0}^{j}) + [\vec{l}(x_{i}^{j+1}) - \vec{l'}(x_{0}^{j+1})] - [(\vec{l}(x_{i}^{j-1}) - \vec{l'}(x_{0}^{j-1})]\] \[= a + b - c.\]

where \(a = 2m^{n-2} - m^{n-1}\mathbb{I}\{j = 0 \text{ or } m-1\}, b = i(m-1)m^{n-2} + m^{n-1}\mathbb{I}\{0 \leq j+1 \leq i-1\},\) and \(c = i(m-1)m^{n-2} + m^{n-1}\mathbb{I}\{0 \leq j-1 \leq i-1\}\) and \(\mathbb{I}\) is the indicator function. Then we can write

\[w_{H_i}(x_i^j) = 2m^{n-2} + m^{n-1} \left[ \mathbb{I}\{0 \le j + 1 \le i - 1\} - \mathbb{I}\{j = 0 \text{ or } m - 1\} - \mathbb{I}\{0 \le j - 1 \le i - 1\} \right].\]

Let \(I = \mathbb{I}\{0 \le j+1 \le i-1\} - \mathbb{I}\{j=0 \text{ or } m-1\} - \mathbb{I}\{0 \le j-1 \le i-1\}\). We will now show that I = -1 when \(j \equiv i\) or \(i-1 \pmod m\) and I = 0 otherwise.

• Case 1. Suppose \(j \equiv i \pmod{m}\). Then since \(j, i \in [m]\), we have j = i and hence I = 1 1 1 = -1 when j = 0 or j = m 1. When \(1 \le j \le m 2\), we have I = 0 0 1 = -1.
• Case 2. Suppose \(j \equiv i 1 \pmod{m}\). Then if j = 0, we have I = 0 1 0 = -1. If j = m 1, we have I = 1 1 1 = -1. If \(1 \le j \le m 2\), we have I = 0 0 1 = -1.
• Case 3. Suppose \(j \not\equiv i, \ i-1 \ (\text{mod } m)\). Then if j=0, we have I=1-1-0=0. If j=m-1, we have I=1-1-0=0. If \(1 \leq j \leq i-2\), we have I=1-0-1=0. If \(i+1 \leq j \leq m-2\), we have I=0-0-0=0, proving the claim.

We have now fully determined the weight induced by the subgraph \(H_i\) for each \(i \in [m]\). We have,

\[w_{H_i}(x_i^j) = \begin{cases} (2-m)m^{n-2}, \ j \equiv i \text{ or } i-1 \pmod{m} \\ 2m^{n-2}, \text{ otherwise} \end{cases}\]

We are ready to determine the weight of each vertex. To this end we have \(w(x_i^j) = w_{H_i}(x_i^j) + \vec{l}(x_{i+1}^j) - \vec{l}(x_{i-1}^j)\) and we recall that the arithmetic is to be performed in \(\mathbb{Z}_{m^n}\).

Case 1. Suppose \(j \equiv i\) or \(i - 1 \pmod{m}\). Then we have

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

since \((i+1)-(i-1)\equiv 2\pmod{m^n}\) when \(1\leq i\leq m-2\) and \((i+1)-(i-1)\equiv 2-m\pmod{m^n}\) when \(i\in\{0,m-1\}\).

Case 2. Suppose \(j \not\equiv i, i-1 \pmod{m}\). Then we have

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Hence, \(w(x_i^j)=2m^{n-1}\) for all \(i,j\in[m]\), so \(G_n\) is orientable \(\mathbb{Z}_{m^n}\)-distance magic for all \(n\geq 1\).

Corollary 3.1. The hypercube \(Q_{2k}\) is orientable \(\mathbb{Z}_{2^{2k}}\)-distance magic for all \(k \geq 1\).

Proof. Since \(Q_{2k} \cong C_4 \square C_4 \square ... \square C_4\), the Cartesian product of k \(C_4\)'s, Theorem 3.1 gives the result.

One may wonder if the hypercube \(Q_{2k+1}\) is orientable \(\mathbb{Z}_{2^{2k+1}}\)-distance magic. Since the graph is odd regular, a little pessimism is understandable. Indeed, no odd regular graph on \(n \equiv 2 \pmod 4\) vertices is orientable \(\mathbb{Z}_n\)-distance magic, as was proved in [2]. However, \(Q_{2k+1}\) contains \(2^{2k+1}\) vertices, a number divisible by 4, so it is possible that \(Q_{2k+1}\) is orientable \(\mathbb{Z}_{2^{2k+1}}\)-distance magic for some k. It can easily be checked that \(Q_1 \cong K_2\) is not. The following theorem rules out \(Q_3\) as well.

Theorem 3.2. The hypercube \(Q_3\) is not orientable \(\mathbb{Z}_8\)-distance magic.

Proof. Let \(G \cong Q_3\) as shown in Figure 1. An important fact we will use is that regardless of the orientation of the edges, the (directed) weight of a given vertex has the same parity as the sum (performed in \(\mathbb{Z}_8\) of course) of its neighbors. Suppose for the sake of contradiction that G is orientable \(\mathbb{Z}_8\)-distance magic with orientable \(\mathbb{Z}_8\)-distance magic labeling \(\vec{l}: V(G) \to \mathbb{Z}_8\) and associated magic constant \(\mu\).

Case 1. Suppose \(\mu\) is even. Observe that \(N(x_1) = \{x_2, x_4, x_6\}\). Then since \(\mu\) is even, either all three of \(\vec{l}(x_2), \vec{l}(x_4), \vec{l}(x_6)\) are even or exactly one is even. Suppose it is the case that all three of \(\vec{l}(x_2), \vec{l}(x_4), \vec{l}(x_6)\) are even. Then that leaves but one other vertex with an even label. Since \(N(x_3) = \{x_2, x_4, x_8\}\), and \(w(x_3) = \mu\) is even, it must be the case that \(\vec{l}(x_8)\) is even.

Figure 1. \(Q_3\)

Consequently, \(\vec{l}(x_1)\), \(\vec{l}(x_3)\), \(\vec{l}(x_5)\) must all be odd. But \(N(x_4) = \{x_1, x_3, x_5\}\), so \(w(x_4) = \mu\) is odd, a contradiction. Therefore, it cannot be the case that all three of \(\vec{l}(x_2)\), \(\vec{l}(x_4)\), \(\vec{l}(x_6)\) are even. In fact, because the graph is vertex transitive, we have shown that no vertex may be adjacent to three even labeled vertices. So it must be the case that every vertex is adjacent to exactly one even-labeled vertex and two odd-labeled vertices. But this is impossible since there are an equal number of odd and even elements in \(\mathbb{Z}_8\).

Case 2. The proof of the odd \(\mu\) case is essentially the same as Case 1 and is left to the reader.

Hence, \(Q_3\) is not orientable \(\mathbb{Z}_8\)-distance magic.

We conclude this section with the following conjecture.

Conjecture 1. The odd-ordered hypercube, \(Q_{2k+1}\) is not orientable \(\mathbb{Z}_{2^{2k+1}}\)-distance magic for any \(k \in \{0, 1, 2, ...\}\).

4. Conclusion

We have proven that any number of disjoint copies of the Cartesian product of two cycles is orientable \(\mathbb{Z}_n\)-distance magic. We have also shown that the Cartesian product of any number of a given cycle is orientable \(\mathbb{Z}_n\)-distance magic, a result which encompasses even-ordered hypercubes. Finally, we have shown that the two smallest odd-ordered hypercubes are not orientable \(\mathbb{Z}_n\)-distance magic graphs, and we conjecture that no odd-ordered hypercube is orientable \(\mathbb{Z}_n\)-distance magic.

Acknowledgement

We would like to thank Dalibor Froncek, University of Minnesota Duluth, for motivating Theorem 3.2 and for his encouragement in general.

References

• [1] S. Arumugam, D. Froncek and N. Kamatchi, Distance magic graphs a survey, J. Indones. Math. Soc. (2011) Special edition, 11–26.
• [2] S. Cichacz, B. Freyberg and D. Froncek, Orientable Zn-distance magic graphs, Discuss. Math. (2017), accepted.
• [3] S. Cichacz and D. Froncek, Distance magic circulant graphs, Discrete Math. 339 (1) (2016), 84–94.
• [4] B. Freyberg and M. Keranen, Orientable Zn-distance magic graphs via products, Preprint.