Petr Kova´ˇr a,b, Matej Krbe ˇ cek ˇ a

^aVSB – Technical University of Ostrava, Department of Applied Mathematics, Czech Republic ˇ b IT4Innovations, VSB – Technical University of Ostrava, Ostrava-Poruba, Czech Republic. ˇ

petr.kovar@vsb.cz, matej.krbecek@vsb.cz

Corresponding author: Petr Kova´rˇ

Let G be a graph with n vertices. By N(v) we denote the set of all vertices adjacent to v. A bijection f : V (G) → {1, 2, . . . , n} is a distance magic labeling of G if there exists an integer k such that the sum of labels of all vertices adjacent to v is k for all vertices v in V (G). A graph which admits a distance magic labeling is a distance magic graph. In this paper, we completely characterize all orders for which a 14-regular distance magic graph exists. Hereby we extended similar results on 2-, 4-, 6-, 8-, 10-, and 12-regular distance magic graphs.

Keywords: Graph labeling, distance magic labeling, 1-VMV labeling

Mathematics Subject Classification : 05C70, 05C78

DOI: 10.5614/ejgta.2024.12.1.4

1. Definitions and known results

Let G be a simple graph with vertex set V and edge set E. The number of vertices we denote by n. A bijection f from V to the set of integers {1, 2, . . . , n} is called a distance magic labeling of G if for every vertex in G the sum of labels of all adjacent vertices equals the same integer k. The sum P u∈N(v) f(u) is the weight w^f (v) of vertex v and k is the magic constant of f. A graph which allows a distance magic labeling is called a distance magic graph.

Results include classification of specific classes as paths, cycles, complete graphs, and wheels, see [11] or also [1, 6]. Distance magic labeling is a well established concept of graph labelings, see the survey paper [1] by Froncek et al. A comprehensive overview on labelings in general is the dy-

Received: 26 January 2019, Revised: 28 September 2023, Accepted: 10 December 2023.

namic survey by Gallian [6]. The notion of distance magic labeling was introduced independently also as 1-vertex magic vertex (or 1-VMV) labeling [11] or sigma labeling (or P-labeling) [7].

All 2-regular distance magic graphs were characterized in [12] and the existence of r-regular distance magic graphs of even order n was completely solved in [4].

Proposition 1.1. An r-regular distance magic graph of even order n exists if and only if 2 ≤ r ≤ n − 2, r ≡ 0 (mod 2) and either n ≡ 0 (mod 4) or n ≡ r + 2 ≡ 2 (mod 4).

An easy counting argument showed that no odd-regular distance magic graph exists (see e.g. [11]) and that the magic constant of an r-regular distance magic graph of order n is k = r(n + 1)/2 ([11, 8]). Later, further papers dealt with distance magic graphs of odd order. Clearly, no 2-regular distance magic graph with 2t+1 vertices exists, because every vertex has weight r(n+1)/2 = 2t+2 and for any vertex adjacent to the vertex labeled t + 1, the second neighbor would also be labeled t + 1, which is not possible. The existence of r-regular distance magic graphs of odd order was settled for r = 4 in [8] and for r = 6, 8, 10, and 12 in [9]. This paper naturally extends the results to r = 14 using similar techniques.

In [5, 10] distance magic graphs of high regularity were examined. Constructions in [5] cover almost all orders for which 14-regular distance magic graphs exist, yet still the existence for certain orders remained open. A single construction for all orders is provided in this paper. Moreover, it yields connected graphs in comparison to [5].

We will use the following result from [10].

Proposition 1.2. An (n − 3)-regular distance magic graph G with n vertices exists if and only if n ≡ 3 (mod 6). Moreover, G is isomorphic to Kn/3[K3].

Recent results on distance magic labeling use group elements for labeling and group operations for evaluating the weights in oriented graphs, see e.g. [3], [2].

2. Odd orders

A 14-regular distance magic graph cannot be too small. Suppose G is a 14-regular distance magic graph of odd order n. Certainly, n > 15, since the complete graph is not distance magic. In Kⁿ the weight of the vertex labeled i is n 2 −i. According to Proposition 1.2 there is no distance magic 14-regular graph with 17 vertices. Immediately, we have the following lemma.

Lemma 2.1. There is no 14-regular distance magic graph of odd order with less than 19 vertices.

The construction of 14-regular distance magic graphs will proceed by induction on the number of vertices. Subgraph A (see Figure 1) will play a crucial role in the construction below.

The vertex set of A is V (A) = {xⁱ , yⁱ : i = 1, 2, . . . , 6}. The edge set E(A) = R ∪ S, where R = {x1x2, x1y2, y1x2, y1y2, x2x6, x2y6, y2x6, y2y6, x3x4, x3y4, y3x4, y3y4, x4x5, x4y5, y4x5, y4y5, x3x5, x3y5, y3x5, y3y5, x1x6, x1y6, y1x6, y1y6} and S = {x2x3, x2y2, y3x2, y2y3, x5x6, x5y6, y5x6, y5y6}. Moreover, the labels assigned to vertices of A in labeling f of G will satisfy the following equations: f(xi) + f(yi) = n + 1 for i = 1, 2, . . . , 6, where n is the order of G.

Edges in R (red edges in Figure 1) will be removed from A in the inductive construction and edges in S (green edges in the Figure 1) will stay untill the next step of the inductive construction.

The inductive step is based on the following lemma.

Figure 1. Subgraph A.

Lemma 2.2. Let G be a 14-regular distance magic graph of odd order n with distance magic labeling f. If G contains subgraph A with f(xi) + f(yi) = n + 1 for i = 1, 2, . . . , 6, then there exists a 14-regular distance magic graph with n + 4 vertices which contains subgraph A′ , where A′ ≃ A.

Proof. Since G is 4-regular and distance magic, the weight of every vertex in f is 7(n + 1). We construct a 14-regular graph G′ with n + 4 vertices along with a distance magic labeling f ′ of G′ so that G′ contains subgraph A′ , where A′ ≃ A, with vertices {x ′ 1 , x′ 2 , . . . , x′ ⁿ} for which the sums of labels f(x ′ i ) + f(y ′ i ) = n + 5, for i = 1, 2, . . . , 6.

Figure 2 shows the addition of four vertices s1, s2, s3, s⁴ to the subgraph A in G. From G we remove all 24 edges in set R (red edges in Figure 2). On the other hand, we add four new vertices s1, s2, s3, s⁴ and 52 new edges (black and blue in Figure 2) in P, where P = {s1x1, s1x2, s1x3, s1x4, s1x5, s1x6, s1y1, s1y2, s1y3, s1y4, s1y5, s1y6, s2x1, s2x2, s2x3, s2x4, s2x5, s2x6, s2y1, s2y2, s2y3, s2y4, s2y5, s2y6, s3x1, s3x2, s3x3, s3x4, s3x5, s3x6, s3y1, s3y2, s3y3, s3y4, s3y5, s3y6, s4x1, s4x2, s4x3, s4x4, s4x5, s4x6, s4y1, s4y2, s4y3, s4y4, s4y5, s4y6, s1s3, s1s4, s2s3, s2s4}

Notice, that G′ is again 14-regular. At every vertex xⁱ and yⁱ for i = 1, 2, . . . , 6 four edges were removed, but four new edges were added to s1, s2, s4, and s4. Also, the four new vertices are joined to all 12 vertices xⁱ and yⁱ for i = 1, 2, . . . , 6, as well as to two vertices among s1, s2, s4, and s4.

We show that the resulting graph G′ with n + 4 vertices has a distance magic labeling as well.

Figure 2. Adding four vertices to a subgraph A, which is subgraph G.

Consider the following labeling \(f'V(G') \rightarrow \{1, 2, \dots, n+4\}\).

\[f'(v) = \begin{cases} f(v) + 2, & \text{for } v \in V(G), \\ 1, & \text{for } v = s_1, \\ n + 4, & \text{for } v = s_2, \\ 2, & \text{for } v = s_3, \\ n + 3, & \text{for } v = s_4. \end{cases}\] (1)

Because 1 and 2 are assigned to the vertices \(s_1\) and \(s_3\), the numbers \(3,4,\ldots,n+2\) are assigned to vertices in V(G) and the remaining integers n+3 and n+4 are assigned to \(s_2\) and \(s_4\), labeling f' is a bijection. Now, we evaluate the weight of every vertex v in G'. For \(s_1\) and \(s_2\) is \(w_{f'}(s_1) = w_{f'}(s_2) = \sum_{i=1}^6 \left(f'(x_i) + f'(y_i)\right) + f'(s_3) + f'(s_4) = 6(n+1) + 12 \cdot 2 + 2 + (n+3) = 7(n+5)\). For \(s_3\) and \(s_4\) the computation is analogous.

The weight of vertices \(x_1\), and \(y_1\) is \(w_{f'}(x_1) = w_{f'}(y_1) = w_f(x_1) + 10 \cdot 2 - f'(x_6) - f'(y_6) - f'(x_2) - f'(y_2) + f'(s_1) + f'(s_2) + f'(s_3) + f'(s_4) = 7(n+1) + 20 - 2(n+1) + 2(n+5) = 7(n+5)\). For vertices \(x_i, y_i\) where \(i = 2, 3, \ldots, 6\) the computation is analogous.

The weight of all remaining vertices v in G' is \(w_{f'}(v) = \sum_{u \in N(v)} f'(u) = \sum_{u \in N(v)} (f(u) + 2) = w_f(u) + 14 \cdot 2 = 7(n+1) + 28 = 7(n+5)\). Therefore f' is a distance magic labeling of G'. Finally, Figure 3 shows subgraph A' in G'. Notice, that \(f'(x_i) + f'(y_i) = n+5\) for \(i=1,2,\ldots,6\) and \(f'(s_1) + f'(s_2) = f'(s_3) + f'(s_4) = n+5\).

3. Main result

Now we are ready to prove our main result.

Theorem 3.1. There exists a 14-regular distance magic graph of odd order n if and only if \(n \ge 19\).

Figure 3. Subgraph A′ in graph G′ .

Proof. By Lemma 2.1 there is no 14-regular distance magic graph of odd order n < 19. 14-regular distance magic graphs with 19 vertices and with 21 vertices are presented in Figures 4 and 5. Both contain subgraph A, which is highlighted. By induction, repeatedly using Lemma 2.2, we construct a 14-regular distance magic graph for all odd orders greater than 21. Thus, the claim holds.

Figure 4. A 14-regular graph with 19 vertices, containing subgraph A.

We expect similar, though more elaborate constructuions to exist also for distance magic graphs of odd order and higher regularities.

Combining Proposition 1.1 and Theorem 3.1 we immediately have the following claim.

Theorem 3.2. There exists a 14-regular distance magic graph of order n if and only if n = 16 or n ≥ 19 and n ≡ 0, 1, 3 (mod 4).

Figure 5. A 14-regular graph with 21 vertices, containing subgraph A.

Acknowledgement

This work was supported by The Ministry of Education, Youth and Sports from the National Programme of Sustainability (NPU II) project "IT4Innovations excellence in science – LQ1602", and it was partially supported by Grant of SGS No. SP2023/011, VSB–Technical University of ˇ Ostrava, Czech Republic.

References

• [1] S. Arumugam, D. Froncek, and N. Kamatchi, Distance Magic Graphs A Survey, ˇ J. Indones. Math. Soc., Special Edition (2011), 11–26.
• [2] S. Cichacz, B. Freyberg, and D. Froncek, Orientable ˇ Zn-distance magic graphs, Discuss. Math. Graph Theory 39 (2019), 533–546.
• [3] B. Freyberg and M. Keranen, Orientable Zn-distance magic labeling of the Cartesian product of many cycles, Electron. J. Graph Theory Appl. 5(2) (2017), 304–311.
• [4] D. Froncek, P. Kov ˇ a´ˇr, and T. Kova´ˇrova, Fair incomplete tournaments, ´ Bull. Inst. Combin. Appl. 48 (2006), 31–33.
• [5] D. Froncek, Fair incomplete tournaments with odd number of teams and large number of ˇ games, Congr. Numer. 187 (2007), 83–89.
• [6] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. DS 6, (2022).
• [7] M.I. Jinnah, On Σ-labelled graphs, In Technical Proceedings of Group Discussion on Graph Labeling Problems (1999), 71–77.
• [8] P. Kova´ˇr, T. Kova´ˇrova, and D. Fron ´ cek, A note on 4-regular distance magic graphs, ˇ Australas. J. Combin. 54 (2012), 127–132.

• [9] P. Kova´ˇr, A. Silber, P. Kabel´ıkova, and M. Krav ´ cenko, On regular distance magic graphs of ˇ odd order, (submitted).
• [10] P. Kova´ˇr and A. Silber, Distance magic graphs of high regularity, AKCE Int. J. Graphs Comb. 9 (2012), 213–219.
• [11] M. Miller, C. Rodger, and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003), 305–315.
• [12] A.A.G. Ngurah and R. Simanjuntak, On distance labelings of 2-regular graphs, Electron. J. Graph Theory Appl. 9(1) (2021), 25–37.