Ravindra Kuber Pawar, Tarkeshwar Singh

Department of Mathematics BITS Pilani K K Birla Goa Campus, Goa, India.

p20200020@goa.bits-pilani.ac.in, tksingh@goa.bits-pilani.ac.in

A graph G = (V, E), where |V (G)| = n and |E(G)| = m is said to be a distance magic graph if there is a bijection f : V (G) → {1, 2, . . . , n} such that the vertex weight w(u) = P v∈N(u) f(v) = k is constant and independent of u, where N(u) is an open neighborhood of the vertex u. The constant k is called a distance magic constant, the function f is called a distance magic labeling of the graph G and the graph which admits such a labeling is called a distance magic graph. In this paper, we present some results on distance magic labeling of Mycielskian graphs.

Keywords: distance magic graphs, Mycielskian graph

Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2024.12.1.7

1. Introduction

Throughout this paper, by a graph G = (V, E), we mean a connected undirected simple graph with vertex set V (G) and edge set E(G), where |V (G)| = n and |E(G)| = m. For graph theoretic terminology and notation we refer to West [15].

A labeling of a graph is any function that assigns elements of a graph (vertices or edges or both) to the set of numbers (positive integers or elements of groups, etc). In particular, if we have a bijection f : V (G) → {1, 2, . . . , |V (G)|}, then f is called a vertex labeling. The neighborhood of a vertex x in G is the set of all the vertices adjacent to x and is denoted by NG(x). The degree of vertex v in G, denoted by dG(v) is |NG(v)|. When a graph G is clear from the context we will

Received: 22 December 2022, Revised: 20 February 2024, Accepted: 7 March 2024.

simply write N(x) and d(x) for neighborhood and degree of a vertex x, respectively. The weight of a vertex v, denoted by w(v) is defined as w(v) = P u∈N(v) f(u). If f is vertex labeling such that w(v) = k, for all v ∈ V (G), then k is called a distance magic constant and labeling f is called a distance magic labeling. The graph which admits such a labeling is called a distance magic graph. For more details see [1, 5, 6, 7, 8, 9, 10, 13, 14].

There are several constructions available for a triangle free graph with chromatic number increase by one in the literature, Mycielski's construction is one of the simplest. Given a triangle free graph G with chromatic number k, Mycielskian of G is the triangle free graph with chromatic number k + 1. For a simple graph G, Mycielski's construction [11] produces a simple graph denoted by µ(G) called Mycielskian graph of G, containing G. Begin with G having vertex set V = {x1, x2, . . . , xn}. The vertex set of µ(G) is V ∪ U ∪ {u}, where U = {y1, y2, . . . , yn} where each yi is an image of xⁱ and E(µ(G)) = E(G) ∪ {yix^j : x^j ∈ NG(xi)} ∪ {uyi}. We call yⁱ an image of vertex xⁱ and we write yⁱ = Im(xi), similarly Im(N(xi)) = {y^j : y^j = Im(x^j ), x^j ∈ N(xi)}. Mycielskian of P³ is shown in Figure 1.

Figure 1. Mycielskian of P3. Figure 2. µ(C5): Grotzsch Graph ¨

The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with an arbitrarily large chromatic number. For example, starting with the graph G = K2, which is triangle-free with χ(G) = 2, we obtain µ(G) = C⁵ a cycle on 5 vertices and χ(C5) = 3. Further µ 2 (G) = µ(µ(G)) = µ(C5) is a Grotzsch graph (see Figure 2) ¨ with the chromatic number 4 and so on. We define µ r (G) ∼= µ(µ r−1 (G)) for r ≥ 1.

Researchers have made few attempts to construct distance magic graphs with specific graphtheoretic properties or to study distance magic property of a specific graph family, see [2, 4, 6, 9, 12]. In this paper, we investigate whether there exists distance magic labeling of Mycielskian of various families of graphs.

Observe that, for a connected graph G with |V (G)| = n and |E(G)| = m, µ(G) is also connected with |V (µ(G))| = 2n + 1, and |E(µ(G)| = 3m + n. Though there are other interesting structural relations between G and µ(G) such as edge connectivity, vertex connectivity, etc., we are not proving them here as they are beyond the interest of this article.

2. Known Results

In this section, we cite some known results on distance magic graphs which are useful for our further investigation. Recall that for non-empty sets A and B, the symmetric difference of A and B, denoted by \(A \triangle B\), is the set \((A \cup B) \setminus (A \cap B)\).

Theorem 2.1. [8, 14] A graph G is not distance magic if there are vertices x and y in G such that \(|N(x)\triangle N(y)| = 1\) or 2.

Theorem 2.2. [10, 13, 14] Let f be a distance magic labeling of a graph G with the vertex set V. Then sum of weights of all the vertices is given by:

\[\sum_{v \in V(G)} w(v) = \sum_{v \in V(G)} d(v)f(v) = kn,\]

where k is the distance magic constant and n is the number of vertices.

Corollary 2.1. [8, 10, 14] No odd regular graph is distance magic.

Theorem 2.3. [10] Cycle \(C_n\) is distance magic if and only if n=4.

3. Main Results

First we discuss some basic structural properties of Mycielskian of a graph such as regularity, degree conditions etc.

Theorem 3.1. Let G be a graph. For any vertex \(x \in V(G)\), \(d_{\mu(G)}(y) = \frac{d_{\mu(G)}(x)}{2} + 1\), where y = Im(x) in \(\mu(G)\).

Proof. Let G be a graph and for any vertex \(x \in V(G)\). By construction \(d_{\mu(G)}(x) = 2d_G(x)\). If y = Im(x) in \(\mu(G)\), then \(N_{\mu(G)}(y) = N_G(x) \cup \{u\}\). This implies \(d_{\mu(G)}(y) = d_G(x) + 1\). Therefore, \(d_{\mu(G)}(y) = \frac{d_{\mu(G)}(x)}{2} + 1\).

Theorem 3.2. Let G be a graph. The Mycielskian of G is regular if and only if \(G \cong K_2\).

Proof. Let G be a graph on n vertices such that \(\mu(G)\) is r-regular. Therefore, for \(x \in V\) and \(y \in U\) we have

\[d_{\mu(G)}(x) = d_{\mu(G)}(y) = d_{\mu(G)}(u) = r.\] (1)

Also, \(N_{\mu(G)}(u) = U\) implies \(d_{\mu(G)}(u) = |U| = n\). Hence,

\[r = n. (2)\]

By Theorem 3.1, we have \(d_{\mu(G)}(y) = \frac{d_{\mu(G)}(x)}{2} + 1\). From Equation (1) we get r=2. Therefore, from Equation (2), we get n=r=2. This means G is a graph on two vertices such that \(\mu(G)\) is 2-regular. There are only two non-isomorphic graphs of order two viz; \(K_2\) and its complement \(\overline{K_2}\). For \(x \in V(\overline{K_2})\), \(d_{\mu(\overline{K_2})}(x) = 0\) and \(d_{\mu(\overline{K_2})}(u) = 2\). Therefore, \(\mu(\overline{K_2})\) is not regular. Hence, \(G \not\cong \overline{K_2}\). The graph \(\mu(K_2)\) is isomorphic to a cycle \(C_5\), which is a 2-regular graph. So, G must be isomorphic to \(K_2\). Conversely if \(G \cong K_2\), then \(\mu(K_2) \cong C_5\) which is 2-regular. This completes the proof.

Now we provide the sufficient conditions on a graph G, for the non-existence of distance magic labeling of its Mycielskian graph.

Lemma 3.1. If a graph G contains two vertices xⁱ and x^j such that |NG(xi)△NG(x^j )| = 1 or 2, then for any r ≥ 1, µ r (G) is not distance magic.

Proof. First we will prove the theorem for r = 1. Let xⁱ and x^j be vertices in G such that |NG(xi)△NG(x^j )| = 1 or 2. Then Nµ(G)(yi) = NG(xi) ∪ {u} and Nµ(G)(y^j ) = NG(x^j ) ∪ {u}. Therefore,

\[N_{\mu(G)}(y_i) \cup N_{\mu(G)}(y_j) = N_G(x_i) \cup N_G(x_j) \cup \{u\} \implies |N_{\mu(G)}(y_i) \triangle N_{\mu(G)}(y_j)| = 1 \text{ or } 2\]

and by Theorem 2.1, µ(G) is not distance magic. For r ≥ 2, suppose that result is true for all positive integers less than or equal to r − 1 and let H = µ r−1 (G). Then by induction hypothesis H has two vertices uⁱ and u^j such that |NH(ui)△NH(u^j )| = 1 or 2. Therefore by proceeding as before we obtain |Nµ(H)(Im(ui))△Nµ(H)(Im(u^j ))| = 1 or 2. Since µ(H) = µ r (G), by Theorem 2.1, we conclude that µ r (G) is not distance magic. This proves the theorem.

Corollary 3.1. The graph µ r (Cn) is not distance magic for n ≥ 5 and r ≥ 1.

Proof. Let Cⁿ be a cycle with vertex set V (Cn) = {x1, x2, . . . , xn}, where n ≥ 5. We prove by contraposition. Consider the neighborhood of two vertices x² and xⁿ then N^Cn (x2) = {x1, x3} and N^Cn (xn) = {x1, xn−1} so that |N^Cn (x2)△N^Cn (xn)| = 2 and by Lemma 3.1, µ r (Cn) is not distance magic for any r ≥ 1.

Lemma 3.2. For a graph G with δ(G) = 1, the Mycielskian graph µ r (G) is not distance magic for any r ≥ 1.

Proof. Let x¹ be a vertex in G such that dG(x1) = 1. Hence, there is an unique vertex x² ∈ NG(x1). Then Nµ(G)(x1) = {x2, y2} and Nµ(G)(y1) = {x2, u} which gives |Nµ(G)(x1)△Nµ(G)(y1)| = |{y2, u}| = 2. Therefore, by Theorem 2.1, µ(G) is not distance magic. Also, as proved earlier, H = µ(G) contains two vertices x¹ and y¹ such that symmetric difference of their neighborhoods is two. Therefore, by Lemma 3.1 µ r (H) is not distance magic for any r ≥ 1. This proves that µ r (G) is not distance magic for any r ≥ 1.

This lemma immediately gives non-existence of distance magic labeling of Mycielskian of a major family of graphs.

Corollary 3.2. If T is a tree, then µ r (T) is not distance magic for any r ≥ 1.

Corollary 3.3. The graph µ r (Pn) is not distance magic for n ≥ 2 and r ≥ 1.

Corollary 3.4. For a complete graph Kn, µ r (Kn) is not distance magic for any r ≥ 1.

Proof. Let x1, x2,. . . , xⁿ be vertices of Kn. For n = 1, µ(K1) ∼= K¹ ∪ K² is not distance magic. So, we assume n ≥ 2. Then, N^Kn (x1) = {x2, x3, . . . , xn} and N^Kn (x2) = {x1, x3, x4, . . . , xn}. Hence, |N^Kn (x1)△N^Kn (x2)| = 2. Therefore, by Lemma 3.1, µ r (Kn) is not distance magic for any r ≥ 1.

Theorem 3.3. The Mycielskian of the wheel Wⁿ = Cⁿ + K¹ is not distance magic for n ≥ 3.

Proof. Let the vertex set V (Wn) = V ∪ U ∪ {u}. Let {x1, x2, . . . , xn} be the set of vertices lying on the rim of Wⁿ and let c¹ be the central vertex, where the subscripts of the rim vertices are taken modulo n. Then, NG(x1) = {x2, xn, c1} and NG(x3) = {x2, x4, c1}. If n ̸= 4, |NG(x1)△NG(x3)| = |{x4, xn}| = 2. Therefore, by Lemma 3.1, the Mycielskian of the wheel Wⁿ = Cⁿ + K¹ is not distance magic for n ̸= 4.

Next, we suppose that n = 4. On contrary suppose that for n = 4, Mycielskian of wheel Wⁿ = Cⁿ + K¹ is distance magic with distance magic labeling f.

Figure 3. Mycielskian of W4.

The Mycielskian of W⁴ is shown in Figure 3. From Figure 3, consider the neighborhoods of vertices in µ(W4):

\[\begin{split} N_{\mu(G)}(x_1) &= \{x_2, \ x_4, \ c_1, \ c_2, \ y_2, \ y_4\} \\ N_{\mu(G)}(x_2) &= \{x_1, \ x_3, \ c_1, \ c_2, \ y_1, \ y_3\} \\ N_{\mu(G)}(y_1) &= \{x_2, \ x_4, \ c_1, \ u\} \\ N_{\mu(G)}(y_2) &= \{x_1, \ x_3, \ c_1, \ u\} \\ N_{\mu(G)}(c_1) &= \{x_1, \ x_2, \ x_3, \ x_4, \ y_1, \ y_2, \ y_3, \ y_4\} \\ N_{\mu(G)}(c_2) &= \{x_1, \ x_2, \ x_3, \ x_4, \ u\} \\ N_{\mu(G)}(u) &= \{y_1, \ y_2, \ y_3, \ y_4, \ c_2\}. \end{split}\]

Now we calculate the weights of vertices as follows:

\[w(x_1) = f(x_2) + f(x_4) + f(c_1) + f(c_2) + f(y_2) + f(y_4)\] \[w(x_2) = f(x_1) + f(x_3) + f(c_1) + f(c_2) + f(y_1) + f(y_3)\] \[w(y_1) = f(x_2) + f(x_4) + f(c_1) + f(u)\] \[w(y_2) = f(x_1) + f(x_3) + f(c_1) + f(u)\] \[w(c_1) = f(x_1) + f(x_2) + f(x_3) + f(x_4) + f(y_1) + f(y_2) + f(y_3) + f(y_4)\] \[w(c_2) = f(x_1) + f(x_2) + f(x_3) + f(x_4) + f(u)\] \[w(u) = f(y_1) + f(y_2) + f(y_3) + f(y_4) + f(c_2).\]

Since, Mycielskian of W⁴ is assumed to be distance magic, we can equate the weights.

\[w(x_1) = w(y_1) \implies f(u) = f(y_2) + f(y_4) + f(c_2)\] (3)

\[w(x_2) = w(y_2) \implies f(u) = f(y_1) + f(y_3) + f(c_2).\] (4)

Form equations (3) and (4) we have

\[f(y_1) + f(y_3) = f(y_2) + f(y_4). (5)\]

Now, w(x1) = w(x2) =⇒ f(x2) + f(x4) + f(y2) + f(y4) = f(x1) + f(x3) + f(y1) + f(y3). By Equation (5) we get, f(x1) + f(x3) = f(x2) + f(x4). Now we assume that

\[f(x_1) + f(x_3) = f(x_2) + f(x_4) = \alpha \tag{6}\]

\[f(y_1) + f(y_3) = f(y_2) + f(y_4) = \beta.\] (7)

By equations (6) and (7), we obtain

\[w(x_1) = \alpha + \beta + f(c_1) + f(c_2)\] \[w(y_1) = \alpha + f(c_1) + f(u)\] \[w(c_1) = 2\alpha + 2\beta\] \[w(c_2) = 2\alpha + f(u)\] \[w(u) = 2\beta + f(c_2).\]

Next we equate the weight of the following vertices:

\[w(y_1) = w(c_2) \implies f(c_1) = \alpha \tag{8}\]

\[w(x_1) = w(u) \implies f(c_1) + \alpha = \beta \tag{9}\]

\[w(u) = w(c_1) \implies f(c_2) = 2\alpha \tag{10}\]

\[w(c_1) = w(c_2) \implies f(u) = 2\beta. \tag{11}\]

From equations (8) and (9) we get, 2α = β. Therefore, by Equation (11), f(u) = 2β = 4α = 4(f(x1) + f(x3)). By assigning smallest labels to x¹ and x² we get f(u) ≥ 4(1 + 2) = 12 which is contradiction to the fact that f(u) ∈ {1, 2, . . . , 11}.

Theorem 3.4. The Mycielskian of cycle Cⁿ is distance magic if and only if n = 4.

Proof. Let Cⁿ be a cycle with vertex set V (Cn) = {x1, x2, . . . , xn}, where n ≥ 3. Suppose that n ̸= 4, then N^Cn (x2) = {x1, x3} and N^Cn (xn) = {x1, xn−1} so that |N^Cn (x2)△N^Cn (xn)| = 2 and by Lemma 3.1, µ(Cn) is not distance magic.

For the converse part consider a cycle on 4 vertices. We label the vertices of µ(C4) as shown in Figure 4. It is easy to see that the weight of each vertex is 18. Hence, µ(C4) is distance magic

Figure 4. Mycielskian of C4.

graph with distance magic constant 18.

Theorem 3.5. µ 2 (C4) is not distance magic.

Proof. From Figure 4, we note the neighborhoods of all the vertices of µ 2 (C4):

\[N(x_1) = N(x_3) = \{x_2, x_4, x_6, x_8, y_2, y_4, y_6, y_8\}\] \[N(x_2) = N(x_4) = \{x_1, x_3, x_5, x_7, y_1, y_3, y_5, y_7\}\] \[N(x_5) = N(x_7) = \{x_2, x_4, x_9, y_2, y_4, y_9\}\] \[N(x_6) = N(x_8) = \{x_1, x_3, x_9, y_1, y_3, y_9\}\] \[N(y_1) = N(y_3) = \{x_2, x_4, x_6, x_8, u\}\] \[N(y_2) = N(y_4) = \{x_1, x_3, x_5, x_7, u\}\] \[N(y_5) = N(y_7) = \{x_2, x_4, x_9, u\}\] \[N(y_6) = N(y_8) = \{x_1, x_3, x_9, u\}\] \[N(x_9) = \{x_5, x_6, x_7, x_8, y_5, y_6, y_7, y_8\}\] \[N(y_9) = \{x_5, x_6, x_7, x_8, u\}\] \[N(u) = \{y_1, y_2, y_3, y_4, y_5, y_6, y_7, y_8, y_9\}.\]

Suppose that µ 2 (C4) is distance magic with distance magic labeling f. Then we can equate the

weights of any two distinct vertices. Equating w(xi) with w(yi), for each i = 1, 2, 5, 6, 9 we obtain

\[f(u) = f(y_2) + f(y_4) + f(y_6) + f(y_8)\] \[= f(y_1) + f(y_3) + f(y_5) + f(y_7)\] \[= f(y_2) + f(y_4) + f(y_9)\] \[= f(y_1) + f(y_3) + f(y_9)\] \[= f(y_5) + f(y_6) + f(y_7) + f(y_8).\]

On simplifying we get f(y9) = f(y1) + f(y3) = f(y2) + f(y4) = f(y5) + f(y7) = f(y6) + f(y8). Since f(u) = f(y2) + f(y4) + f(y6) + f(y8), we get f(u) = 2f(y9). Now, equating w(y5) with w(y6), w(y2) with w(y9), w(y1) with w(y9), and w(y1) with w(y5) we obtain the following equalities

\[f(x_1) + f(x_3) = f(x_2) + f(x_4)\] \[f(x_1) + f(x_3) = f(x_6) + f(x_8)\] \[f(x_2) + f(x_4) = f(x_5) + f(x_7)\] \[f(x_6) + f(x_8) = f(x_9)\]

respectively. Which gives f(x9) = f(x1) + f(x3) = f(x2) + f(x4) = f(x5) + f(x7) = f(x6) + f(x8). There are 19 vertices in µ 2 (C4). The sum of all vertex labels is

\[\sum_{i=1}^{9} f(x_i) + \sum_{i=1}^{9} f(y_i) + f(u) = 190\] \[\implies 5f(x_9) + 7f(y_9) = 190.\]

Which is a Diophantine equation and all of its possible non-negative integer solutions in the form (x9, y9) are:

\[(3, 25), (10, 20), (17, 15), (24, 10), (31, 5), (38, 0).\]

But 1 ≤ f(x) ≤ 19, the only possible solution is f(x9) = 17 and f(y9) = 15. This gives f(u) = 2f(y9) > 19, which is not possible. Hence, µ 2 (C4) is not a distance magic.

Theorem 3.6. The Mycielskian of a complete bipartite graph Km,n is distance magic if and only if m = n = 2.

Proof. Let G ∼= Km,n, where m and n both are at least 2. Otherwise, G will be a star and by Lemma 3.2, it is not distance magic. Let V¹ = {x11, x12, . . . , x1m} and V² = {x21, x22, . . . , x2n} be the partition of vertex set of G. Then as per our convention y1ⁱ = Im(x1i) and y2^j = Im(x2^j ). On the contrary suppose that, Mycielskian graph µ(G) is distance magic with distance magic labeling f. Now, let us find the neighborhood of each vertex in µ(G).

\[\begin{split} N_{\mu(G)}(x_{1i}) &= \{x_{2j}, y_{2j} : 1 \leq j \leq n\} \text{ for each } 1 \leq i \leq m \\ N_{\mu(G)}(x_{2j}) &= \{x_{1i}, y_{1i} : 1 \leq i \leq m\} \text{ for each } 1 \leq j \leq n \\ N_{\mu(G)}(y_{1i}) &= \{u, x_{2j} : 1 \leq j \leq n\} \text{ for each } 1 \leq i \leq m \\ N_{\mu(G)}(y_{2j}) &= \{u, x_{1i} : 1 \leq i \leq m\} \text{ for each } 1 \leq j \leq n \\ N_{\mu(G)}(u) &= \{y_{1i}, y_{2j} : 1 \leq i \leq m \text{ and } 1 \leq j \leq n\}. \end{split}\]

Assume that

\[\sum_{i=1}^{m} f(x_{1i}) = \alpha, \ \sum_{j=1}^{n} f(x_{2j}) = \beta, \ \sum_{i=1}^{m} f(y_{1i}) = \gamma, \ \sum_{j=1}^{n} f(y_{2j}) = \delta.\] (12)

Then the weights of the vertices are as follows:

\[w(x_{1i}) = \sum_{j=1}^{n} f(x_{2j}) + \sum_{j=1}^{n} f(y_{2j}) = \beta + \delta \text{ for each } 1 \le i \le m\] \[w(x_{2j}) = \sum_{i=1}^{m} f(x_{1i}) + \sum_{i=1}^{m} f(y_{1i}) = \alpha + \gamma \text{ for each } 1 \le j \le n\] \[w(y_{1i}) = \sum_{j=1}^{n} f(x_{2j}) + f(u) = \beta + f(u) \text{ for each } 1 \le i \le m\] \[w(y_{2j}) = \sum_{i=1}^{m} f(x_{1i}) + f(u) = \alpha + f(u) \text{ for each } 1 \le j \le n\] \[w(u) = \sum_{i=1}^{m} f(y_{1i}) + \sum_{j=1}^{n} f(y_{2j}) = \gamma + \delta.\]

Since, the Mycielskian graph µ(G) is distance magic, the vertex weights are the same under f i.e.

\[\beta + \delta = \alpha + \gamma = \beta + f(u) = \alpha + f(u) = \gamma + \delta.\]

From the above equations we get,

\[\alpha = \beta = \gamma = \delta = f(u). \tag{13}\]

The vertex u must receive the largest label, that is, f(u) = 2(m + n) + 1. Otherwise, one of the vertex x1ⁱ , x2ⁱ , y1^j or y2^j for some i or j will receive the label 2(m + n) + 1 and one of the equalities

\[\alpha = f(u), \ \beta = f(u), \ \gamma = f(u), \ \delta = f(u)\]

is not possible. Therefore, from Equation (13) we have

\[\alpha + \beta + \gamma + \delta = 4f(u). \tag{14}\]

Since, f(u) = 2(m + n) + 1, α + β + γ + δ is the sum of the first 2(m + n) natural numbers, and Equation (14) becomes

\[\frac{2(m+n)[2(m+n)+1]}{2} = 4[2(m+n)+1].\]

This implies m + n = 4. Since, m and n both are at least 2, we must have m = n = 2.

Conversely, suppose that m = n = 2. In this case Km,n ∼= C⁴ and by Theorem 3.4, µ(C4) is distance magic. This completes the proof.

Theorem 3.7. If G is an r-regular graph such that the Mycielskian graph µ(G) is distance magic, then r ≤ 3.

Proof. Let G be an r-regular graph such that its Mycielskian graph µ(G) admits a distance magic labeling f. Then dµ(G)(xi) = 2r, dµ(G)(yi) = r + 1 and dµ(G)(u) = n. Also, the sum of the weight of all the vertices xⁱ is

\[\sum_{i=1}^{n} w(x_i) = r \sum_{i=1}^{n} f(x_i) + r \sum_{i=1}^{n} f(y_i) = kn\] (15)

and those of yⁱ is

\[\sum_{i=1}^{n} w(y_i) = r \sum_{i=1}^{n} f(x_i) + nf(u) = kn.\] (16)

From Equation (15) and Equation (16), we obtain

\[r\sum_{i=1}^{n} f(y_i) = nf(u).\] (17)

If we assign the smallest labels ¹, ², ³, . . . , n to the vertices ^y1, y2, . . . , yn, then we get ⁿ(ⁿ + 1) 2 ≤ Xn i=1 f(yi) and we know that f(u) ≤ 2n + 1. Using these inequalities in Equation (17), we get

\[\frac{rn(n+1)}{2} \le n(2n+1) \implies r \le 4 - \frac{2}{n+1}.\]

Since, n is at least 1, r ≤ 3. This completes the proof.

Thus, it is clear that if G is an r-regular graph such that the Mycielskian graph µ(G) admits a distance magic labeling, then r ∈ {1, 2, 3}. If G is 1-regular graph then δ(G) = 1. Therefore, by Lemma 3.2, µ(G) is not distance magic. Therefore, r must be either 2 or 3. Theorem 3.4 gives a complete characterization of distance magic labeling of Mycielskian of connected 2−regular graphs.

Now we discuss the existence of distance magic labeling of Mycielskian of connected 3-regular graphs of order up to 8. The smallest 3-regular graph is K⁴ and by Corollary 3.4, Mycielskian of K⁴ is not distance magic.

Lemma 3.3. The Mycielskian of a 3-regular graph of order 6 is not distance magic.

Proof. There are 2 graphs of order 6 that are 3-regular as shown in Figure 5. One of them is isomorphic to K3,³ and hence by Theorem 3.6, Mycielskian of K3,³ is not distance magic. For Mycielskian of graph G as shown in Figure 5(b), consider N(a) = {b, d, f} and N(c) = {b, d, e}. Therefore, NG(a)△NG(c) = {e, f} which implies |NG(a)△NG(c)| = 2 and by Lemma 3.1, Mycielskian of this graph is not distance magic. This proves the lemma.

Figure 5. 3-regular graphs of order 6.

Lemma 3.4. The Mycielskian of a 3-regular graph of order 8 is not distance magic.

Proof. Since, we know that there are five 3-regular graphs of order 8 [3], denoted by G1, G2, G3, G4, G⁵ as shown in Figure 6. To apply Lemma 3.1 for each of these graphs we identify two vertices u and v in each graph to get 2 as the size of symmetric difference N(u)△N(v) as follows:

• 1. In graph G1, N(a)△N(g) = {b, d} and hence |N(a)△N(g)| = 2.
• 2. In graph G2, N(a)△N(b) = {a, b} and hence |N(a)△N(b)| = 2.
• 3. In graph G3, N(b)△N(g) = {a, f} and hence |N(b)△N(g)| = 2.
• 4. In graph G4, N(c)△N(g) = {b, h} and hence |N(c)△N(g)| = 2.
• 5. In graph G5, N(a)△N(d) = {b, c} and hence |N(a)△N(d)| = 2.

Then by Lemma 3.1, Mycielskian of a 3-regular graph of order 8 is not distance magic.

Theorem 3.8. The Mycielskian of 3-regular graph G of order ≤ 8 is not distance magic.

Proof. Proof follows from Corollary 3.4, Lemma 3.3 and Lemma 3.4.

There are nineteen 3-regular graphs of order 10 [3]. We consider the Petersen graph—the best-known graph in this family.

Theorem 3.9. The Mycielskian of the Petersen graph is not distance magic.

Proof. Let G denote the Petersen graph as shown in Figure 7. On contrary suppose that Mycielskian of Petersen admits distance magic labeling f. Then the neighborhoods of vertices y1, y4, y7, y⁸ in µ(G) as shown in Figure 7 are:

Figure 6. 3-regular graphs of order 8.

\[N_{\mu(G)}(y_1) = \{x_2, x_5, x_6, u\}\] \[N_{\mu(G)}(y_4) = \{x_3, x_5, x_9, u\}\] \[N_{\mu(G)}(y_7) = \{x_2, x_9, x_{10}, u\}\] \[N_{\mu(G)}(y_8) = \{x_3, x_6, x_{10}, u\}.\]

Hence, their weights are given by,

\[w(y_1) = f(x_2) + f(x_5) + f(x_6) + f(u)\] \[w(y_4) = f(x_3) + f(x_5) + f(x_9) + f(u)\] \[w(y_7) = f(x_2) + f(x_9) + f(x_{10}) + f(u)\] \[w(y_8) = f(x_3) + f(x_6) + f(x_{10}) + f(u).\]

Since, all weights are same, w(y1) = w(y7) gives

\[f(x_5) + f(x_6) = f(x_9) + f(x_{10})\] (18)

and w(y4) = w(y8) gives

\[f(x_5) + f(x_9) = f(x_6) + f(x_{10}). (19)\]

Subtracting Equation (18) from Equation (19) we obtain a contradiction f(x6) = f(x9).

Figure 7. Petersen Graph.

Proposition 3.1. Let G be a graph. If µ(G) is a regular graph, then µ(G) is not distance magic.

Proof. Let G be a graph on n vertices such that µ(G) is r-regular. Then by Theorem 3.2, G ∼= K2. But µ(K2) ∼= C⁵ and by Theorem 2.3, C⁵ is not distance magic. This completes the proof.

Observation 1. The graph G and its Mycielskian µ(G) do not share the property of being distance magic, i.e. µ(G) is distance magic irrespective of G, e.g., the path on 3 vertices P³ is distance magic [10] but µ r (P3) is not distance magic for any r ≥ 1 (see Corollary 3.2). Whereas, C⁴ is distance magic [10] and µ(C4) is also distance magic (see Theorem 3.4) but µ 2 (C4) is not distance magic.

4. Conclusion and Future Scope

It remains to find other classes of graphs whose Mycielskian is distance magic. To construct distance magic graphs of arbitrarily large chromatic number by Mycielskians construction we need a graph G such that µ r (G) is distance magic, for all r ≥ 1 but Observation 1, makes it hard to think of such a graph G.

Acknowledgement

Authors are thankful to the Science and Engineering Research Board (Ref. No. CRG/2018/002536), Government of India, for providing financial support. Also, authors are thankful to the referees for their invaluable comments.

References

• [1] S. Arumugam, D. Froncek, and N. Kamatchi, Distance magic graphs a survey, ˇ Journal of the Indonesian Mathematical Society, Special Edition (2011), 11–26.
• [2] S. Cichacz and D. Froncek, Distance magic circulant graphs, ˇ Discrete Mathematics 339(1) (2016), 84–94.
• [3] F. Bussemaker, C. Cobeljic, J. Seidel, and D. Cvetkovic, Cubic graphs on ≤ 14 vertices, Journal of Combinatorial Theory, Series B, 23(2) (1977), 234–235.
• [4] B. Freyberg and K. Melissa, Orientable Zn-distance magic labeling of the Cartesian product of many cycles, Electronic Journal of Graph Theory and Applications 5(2) (2017), 304 – 311.
• [5] J.A. Gallian, Dynamic survey of graph labeling, Electronic Journal of Combinatorics # DS6, (2020), 1–445.
• [6] A. Godinho, Studies in Neighborhood Magic Graphs, Ph.D. Thesis (2020), Birla Institute of Technology and Science, Pilani, India.
• [7] A. Handa, Studies in Distance Antimagic Graphs, Ph.D. Thesis (2021), Birla Institute of Technology and Science, Pilani, India.
• [8] M.I. Jinnah, On Σ-labelled graphs, Technical Proceedings of Group Discussion on Graph labeling Problems, eds. B.D. Acharya and S.M. Hedge, (1999), 71–77.
• [9] P. Kova´ˇr, D. Froncek, and T. Kov ˇ a´ˇrova, A note on 4-regular distance magic graphs, ´ Australasian Journal of Combinatorics 54(2) (2012), 127–132.
• [10] M. Miller, C. Rodger, and R. Simanjuntak, Distance magic labelings of graphs, Australian Journal of Combinatorics, 28 (2003), 305–315.
• [11] J. Mycielski, Sur le coloriage des graphes, Coll. Math. 3(1995), 161–162.
• [12] A.V. Prajeesh, K. Paramasivam, and K.M. Kathiresan, On distance magic Harary hraphs, Utilitas Mathematica 115 (2020), 251–266.
• [13] S.B. Rao and T. Singh, Sigma graphs a survey, Labelings of Discrete Structures and Applications (eds. B.D. Acharya, S. Arumugam and A. Rosa, Narosa Publishing House, New Delhi), (2008), 135–140.
• [14] V. Vilfred, Σ-Labelled Graphs, and Circulant Graphs, Ph.D. Thesis (1994), University of Kerala, Trivandrum, India.
• [15] D.B. West, Introduction to Graph Theory, Pearson Education Second Edition (1995).