Electronic Journal of Graph Theory and Applications 12 .
, 75Ae88 Distance magic labelling of Mycielskian graphs Ravindra Kuber Pawar.
Tarkeshwar Singh Department of Mathematics BITS Pilani K K Birla Goa Campus.
Goa.
India.
p20200020@goa.
bits-pilani.
in, tksingh@goa.
bits-pilani.
Abstract A graph G = (V.
E), where |V (G)| = n and |E(G)| = m is said to be a distancePmagic graph if there is a bijection f : V (G) Ie .
, 2, .
, .
such that the vertex weight w.
= vOON .
= k is constant and independent of u, where N .
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.
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 .
A labeling of a graph is any function that assigns elements of a graph .
ertices or edges or bot.
to the set of numbers .
ositive integers or elements of groups, et.
In particular, if we have a bijection f : V (G) Ie .
, 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 .
The degree of vertex v in G, denoted by dG .
is |NG .
When a graph G is clear from the context we will Received: 22 December 2022.
Revised: 20 February 2024.
Accepted: 7 March 2024.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh simply write N .
and d.
for neighborhood and degree of a vertex x, respectively.
The weight of a vertex v, denoted by w.
is defined as w.
= uOON .
If f is vertex labeling such that w.
= k, for all v OO 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 .
, 5, 6, 7, 8, 9, 10, 13, .
There are several constructions available for a triangle free graph with chromatic number increase by one in the literature.
MycielskiAos 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.
MycielskiAos construction .
produces a simple graph denoted by AA(G) called Mycielskian graph of G, containing G.
Begin with G having vertex set V = .
1 , x2 , .
, xn }.
The vertex set of AA(G) is V O U O .
, where U = .
1 , y2 , .
, yn } where each yi is an image of xi and E(AA(G)) = E(G) O .
i xj : xj OO NG .
i )} O .
yi }.
We call yi an image of vertex xi and we write yi = Im.
i ), similarly Im(N .
i )) = .
j : yj = Im.
j ), xj OO N .
i )}.
Mycielskian of P3 is shown in Figure 1.
Figure 1.
Mycielskian of P3 .
Figure 2.
AA(C5 ): GroOtzsch 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 N(G) = 2, we obtain AA(G) = C5 a cycle on 5 vertices and N(C5 ) = 3.
Further AA2 (G) = AA(AA(G)) = AA(C5 ) is a GroOtzsch graph .
ee Figure .
with the chromatic number 4 and so on.
We define AAr (G) O = AA(AArOe1 (G)) for r Ou 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 .
, 4, 6, 9.
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.
AA(G) is also connected with |V (AA(G))| = 2n 1, and |E(AA(G)| = 3m n.
Though there are other interesting structural relations between G and AA(G) such as edge connectivity, vertex connectivity, etc.
, we are not proving them here as they are beyond the interest of this article.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh 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 AnB, is the set (A O B) \ (A O B).
Theorem 2.
, .
A graph G is not distance magic if there are vertices x and y in G such that |N .
nN .
| = 1 or 2.
Theorem 2.
, 13, .
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:
= d.
= kn, vOOV (G) vOOV (G) where k is the distance magic constant and n is the number of vertices.
Corollary 2.
, 10, .
No odd regular graph is distance magic.
Theorem 2.
Cycle Cn is distance magic if and only if n = 4.
Main Results First we discuss some basic structural properties of Mycielskian of a graph such as regularity, degree conditions etc.
Theorem 3.
Let G be a graph.
For any vertex x OO V (G), dAA(G) .
= y = Im.
in AA(G).
dAA(G) .
1, where Proof.
Let G be a graph and for any vertex x OO V (G).
By construction dAA(G) .
= 2dG .
y = Im.
in AA(G), then NAA(G) .
= NG .
This implies dAA(G) .
= dG .
Therefore, .
dAA(G) .
= AA(G) 1.
Theorem 3.
Let G be a graph.
The Mycielskian of G is regular if and only if G O = K2 .
Proof.
Let G be a graph on n vertices such that AA(G) is r-regular.
Therefore, for x OO V and y OO U we have dAA(G) .
= dAA(G) .
= dAA(G) .
= r.
Also.
NAA(G) .
= U implies dAA(G) .
= |U | = n.
Hence, r = n.
By Theorem 3.
1, we have dAA(G) .
= AA(G) 1.
From Equation .
we get r = 2.
Therefore, from Equation .
, we get n = r = 2.
This means G is a graph on two vertices such that AA(G) is 2-regular.
There are only two non-isomorphic graphs of order two viz.
K2 and its complement K2 .
For x OO V (K2 ), dAA(K2 ) .
= 0 and dAA(K2 ) .
= 2.
Therefore.
AA(K2 ) is not regular.
Hence.
GO = K2 .
The graph AA(K2 ) is isomorphic to a cycle C5 , which is a 2-regular graph.
So.
G must be isomorphic to K2 .
Conversely if G O = K2 , then AA(K2 ) O = C5 which is 2-regular.
This completes the proof.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Now we provide the sufficient conditions on a graph G, for the non-existence of distance magic labeling of its Mycielskian graph.
Lemma 3.
If a graph G contains two vertices xi and xj such that |NG .
i )nNG .
j )| = 1 or 2, then for any r Ou 1.
AAr (G) is not distance magic.
Proof.
First we will prove the theorem for r = 1.
Let xi and xj be vertices in G such that |NG .
i )nNG .
j )| = 1 or 2.
Then NAA(G) .
i ) = NG .
i ) O .
and NAA(G) .
j ) = NG .
j ) O .
Therefore.
NAA(G) .
i ) O NAA(G) .
j ) = NG .
i ) O NG .
j ) O .
=Ne |NAA(G) .
i )nNAA(G) .
j )| = 1 or 2 and by Theorem 2.
AA(G) is not distance magic.
For r Ou 2, suppose that result is true for all positive integers less than or equal to r Oe 1 and let H = AArOe1 (G).
Then by induction hypothesis H has two vertices ui and uj such that |NH .
i )nNH .
j )| = 1 or 2.
Therefore by proceeding as before we obtain |NAA(H) (Im.
i ))nNAA(H) (Im.
j ))| = 1 or 2.
Since AA(H) = AAr (G), by Theorem 1, we conclude that AAr (G) is not distance magic.
This proves the theorem.
Corollary 3.
The graph AAr (Cn ) is not distance magic for n Ou 5 and r Ou 1.
Proof.
Let Cn be a cycle with vertex set V (Cn ) = .
1 , x2 , .
, xn }, where n Ou 5.
We prove by Consider the neighborhood of two vertices x2 and xn then NCn .
2 ) = .
1 , x3 } and NCn .
n ) = .
1 , xnOe1 } so that |NCn .
2 )nNCn .
n )| = 2 and by Lemma 3.
AAr (Cn ) is not distance magic for any r Ou 1.
Lemma 3.
For a graph G with (G) = 1, the Mycielskian graph AAr (G) is not distance magic for any r Ou 1.
Proof.
Let x1 be a vertex in G such that dG .
1 ) = 1.
Hence, there is an unique vertex x2 OO NG .
1 ).
Then NAA(G) .
1 ) = .
2 , y2 } and NAA(G) .
1 ) = .
2 , .
which gives |NAA(G) .
1 )nNAA(G) .
1 )| = |.
2 , .
| = 2.
Therefore, by Theorem 2.
AA(G) is not distance magic.
Also, as proved earlier.
H = AA(G) contains two vertices x1 and y1 such that symmetric difference of their neighborhoods is two.
Therefore, by Lemma 3.
1 AAr (H) is not distance magic for any r Ou 1.
This proves that AAr (G) is not distance magic for any r Ou 1.
This lemma immediately gives non-existence of distance magic labeling of Mycielskian of a major family of graphs.
Corollary 3.
If T is a tree, then AAr (T ) is not distance magic for any r Ou 1.
Corollary 3.
The graph AAr (Pn ) is not distance magic for n Ou 2 and r Ou 1.
Corollary 3.
For a complete graph Kn .
AAr (Kn ) is not distance magic for any r Ou 1.
Proof.
Let x1 , x2 ,.
, xn be vertices of Kn .
For n = 1.
AA(K1 ) O = K1 O K2 is not distance magic.
So, we assume n Ou 2.
Then.
NKn .
1 ) = .
2 , x3 , .
, xn } and NKn .
2 ) = .
1 , x3 , x4 , .
, xn }.
Hence, |NKn .
1 )nNKn .
2 )| = 2.
Therefore, by Lemma 3.
AAr (Kn ) is not distance magic for any r Ou 1.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Theorem 3.
The Mycielskian of the wheel Wn = Cn K1 is not distance magic for n Ou 3.
Proof.
Let the vertex set V (Wn ) = V O U O .
Let .
1 , x2 , .
, xn } be the set of vertices lying on the rim of Wn and let c1 be the central vertex, where the subscripts of the rim vertices are taken modulo n.
Then.
NG .
1 ) = .
2 , xn , c1 } and NG .
3 ) = .
2 , x4 , c1 }.
If n = 4, |NG .
1 )nNG .
3 )| = |.
4 , xn }| = 2.
Therefore, by Lemma 3.
1, the Mycielskian of the wheel Wn = Cn K1 is not distance magic for n = 4.
Next, we suppose that n = 4.
On contrary suppose that for n = 4.
Mycielskian of wheel Wn = Cn K1 is distance magic with distance magic labeling f .
Figure 3.
Mycielskian of W4 .
The Mycielskian of W4 is shown in Figure 3.
From Figure 3, consider the neighborhoods of vertices in AA(W4 ):
NAA(G) .
1 ) = .
2 , x4 , c1 , c2 , y2 , y4 } NAA(G) .
2 ) = .
1 , x3 , c1 , c2 , y1 , y3 } NAA(G) .
1 ) = .
2 , x4 , c1 , .
NAA(G) .
2 ) = .
1 , x3 , c1 , .
NAA(G) .
1 ) = .
1 , x2 , x3 , x4 , y1 , y2 , y3 , y4 } NAA(G) .
2 ) = .
1 , x2 , x3 , x4 , .
NAA(G) .
= .
1 , y2 , y3 , y4 , c2 }.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Now we calculate the weights of vertices as follows:
1 ) = f .
2 ) f .
4 ) f .
1 ) f .
2 ) f .
2 ) f .
4 ) w.
2 ) = f .
1 ) f .
3 ) f .
1 ) f .
2 ) f .
1 ) f .
3 ) w.
1 ) = f .
2 ) f .
4 ) f .
1 ) f .
2 ) = f .
1 ) f .
3 ) f .
1 ) f .
1 ) = f .
1 ) f .
2 ) f .
3 ) f .
4 ) f .
1 ) f .
2 ) f .
3 ) f .
4 ) w.
2 ) = f .
1 ) f .
2 ) f .
3 ) f .
4 ) f .
= f .
1 ) f .
2 ) f .
3 ) f .
4 ) f .
2 ).
Since.
Mycielskian of W4 is assumed to be distance magic, we can equate the weights.
1 ) = w.
1 ) =Ne f .
= f .
2 ) f .
4 ) f .
2 ) w.
2 ) = w.
2 ) =Ne f .
= f .
1 ) f .
3 ) f .
2 ).
Form equations .
we have f .
1 ) f .
3 ) = f .
2 ) f .
4 ).
Now, w.
1 ) = w.
2 ) =Ne f .
2 ) f .
4 ) f .
2 ) f .
4 ) = f .
1 ) f .
3 ) f .
1 ) f .
3 ).
Equation .
we get, f .
1 ) f .
3 ) = f .
2 ) f .
4 ).
Now we assume that f .
1 ) f .
3 ) = f .
2 ) f .
4 ) = f .
1 ) f .
3 ) = f .
2 ) f .
4 ) = .
By equations .
, we obtain w.
1 ) = f .
1 ) f .
2 ) w.
1 ) = f .
1 ) f .
1 ) = 2 2 w.
2 ) = 2 f .
= 2 f .
2 ).
Next we equate the weight of the following vertices:
1 ) = w.
2 ) =Ne f .
1 ) = w.
1 ) = w.
=Ne f .
1 ) = w.
= w.
1 ) =Ne f .
2 ) = 2 w.
1 ) = w.
2 ) =Ne f .
= 2.
From equations .
we get, 2 = .
Therefore, by Equation .
, f .
= 2 = 4 = 4.
1 ) f .
3 )).
By assigning smallest labels to x1 and x2 we get f .
Ou 4.
= 12 which is contradiction to the fact that f .
OO .
, 2, .
, .
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Theorem 3.
The Mycielskian of cycle Cn is distance magic if and only if n = 4.
Proof.
Let Cn be a cycle with vertex set V (Cn ) = .
1 , x2 , .
, xn }, where n Ou 3.
Suppose that n = 4, then NCn .
2 ) = .
1 , x3 } and NCn .
n ) = .
1 , xnOe1 } so that |NCn .
2 )nNCn .
n )| = 2 and by Lemma 3.
AA(Cn ) is not distance magic.
For the converse part consider a cycle on 4 vertices.
We label the vertices of AA(C4 ) as shown in Figure 4.
It is easy to see that the weight of each vertex is 18.
Hence.
AA(C4 ) is distance magic Figure 4.
Mycielskian of C4 .
graph with distance magic constant 18.
Theorem 3.
AA2 (C4 ) is not distance magic.
Proof.
From Figure 4, we note the neighborhoods of all the vertices of AA2 (C4 ):
N .
1 ) = N .
3 ) = .
2 , x4 , x6 , x8 , y2 , y4 , y6 , y8 } N .
2 ) = N .
4 ) = .
1 , x3 , x5 , x7 , y1 , y3 , y5 , y7 } N .
5 ) = N .
7 ) = .
2 , x4 , x9 , y2 , y4 , y9 } N .
6 ) = N .
8 ) = .
1 , x3 , x9 , y1 , y3 , y9 } N .
1 ) = N .
3 ) = .
2 , x4 , x6 , x8 , .
N .
2 ) = N .
4 ) = .
1 , x3 , x5 , x7 , .
N .
5 ) = N .
7 ) = .
2 , x4 , x9 , .
N .
6 ) = N .
8 ) = .
1 , x3 , x9 , .
N .
9 ) = .
5 , x6 , x7 , x8 , y5 , y6 , y7 , y8 } N .
9 ) = .
5 , x6 , x7 , x8 , .
N .
= .
1 , y2 , y3 , y4 , y5 , y6 , y7 , y8 , y9 }.
Suppose that AA2 (C4 ) is distance magic with distance magic labeling f .
Then we can equate the Distance magic labelling of Mycielskian graphs Pawar and T.
Singh weights of any two distinct vertices.
Equating w.
i ) with w.
i ), for each i = 1, 2, 5, 6, 9 we obtain f .
= f .
2 ) f .
4 ) f .
6 ) f .
8 ) = f .
1 ) f .
3 ) f .
5 ) f .
7 ) = f .
2 ) f .
4 ) f .
9 ) = f .
1 ) f .
3 ) f .
9 ) = f .
5 ) f .
6 ) f .
7 ) f .
8 ).
On simplifying we get f .
9 ) = f .
1 ) f .
3 ) = f .
2 ) f .
4 ) = f .
5 ) f .
7 ) = f .
6 ) f .
8 ).
Since f .
= f .
2 ) f .
4 ) f .
6 ) f .
8 ), we get f .
= 2f .
9 ).
Now, equating w.
5 ) with w.
6 ), w.
2 ) with w.
9 ), w.
1 ) with w.
9 ), and w.
1 ) with w.
5 ) we obtain the following f .
1 ) f .
3 ) = f .
2 ) f .
4 ) f .
1 ) f .
3 ) = f .
6 ) f .
8 ) f .
2 ) f .
4 ) = f .
5 ) f .
7 ) f .
6 ) f .
8 ) = f .
9 ) Which gives f .
9 ) = f .
1 ) f .
3 ) = f .
2 ) f .
4 ) = f .
5 ) f .
7 ) = f .
6 ) f .
8 ).
There are 19 vertices in AA2 (C4 ).
The sum of all vertex labels is f .
i ) f .
i ) f .
= 190 =Ne 5f .
9 ) 7f .
9 ) = 190.
Which is a Diophantine equation and all of its possible non-negative integer solutions in the form .
9 , y9 ) are:
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
But 1 O f .
O 19, the only possible solution is f .
9 ) = 17 and f .
9 ) = 15.
This gives f .
= 2f .
9 ) > 19, which is not possible.
Hence.
AA2 (C4 ) is not a distance magic.
Theorem 3.
The Mycielskian of a complete bipartite graph Km,n is distance magic if and only if m = n = 2.
Proof.
Let G O = 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 V1 = .
11 , x12 , .
, x1m } and V2 = .
21 , x22 , .
, x2n } be the partition of vertex set of G.
Then as per our convention y1i = Im.
1i ) and y2j = Im.
2j ).
On the contrary suppose that.
Mycielskian graph AA(G) is distance magic with distance magic labeling f .
Now, let us find the neighborhood of each vertex in AA(G).
NAA(G) .
1i ) = .
2j , y2j : 1 O j O .
for each 1 O i O m NAA(G) .
2j ) = .
1i , y1i : 1 O i O .
for each 1 O j O n NAA(G) .
1i ) = .
, x2j : 1 O j O .
for each 1 O i O m NAA(G) .
2j ) = .
, x1i : 1 O i O .
for each 1 O j O n NAA(G) .
= .
1i , y2j : 1 O i O m and 1 O j O .
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Assume that f .
1i ) = , f .
2j ) = , f .
1i ) = , f .
2j ) = .
Then the weights of the vertices are as follows:
1i ) = w.
2j ) = f .
2j ) f .
1i ) w.
1i ) = f .
2j ) = for each 1 O i O m f .
1i ) = for each 1 O j O n f .
2j ) f .
= f .
for each 1 O i O m w.
2j ) = f .
1i ) f .
= f .
for each 1 O j O n w.
= f .
1i ) f .
2j ) = .
Since, the Mycielskian graph AA(G) is distance magic, the vertex weights are the same under f = = f .
= f .
= .
From the above equations we get, = = = = f .
The vertex u must receive the largest label, that is, f .
= 2.
Otherwise, one of the vertex x1i , x2i , y1j or y2j for some i or j will receive the label 2.
1 and one of the = f .
, = f .
, = f .
, = f .
is not possible.
Therefore, from Equation .
we have = 4f .
Since, f .
= 2.
1, is the sum of the first 2.
natural numbers, and Equation .
= 4.
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 O = C4 and by Theorem 3.
AA(C4 ) is distance magic.
This completes the proof.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh Theorem 3.
If G is an r-regular graph such that the Mycielskian graph AA(G) is distance magic, then r O 3.
Proof.
Let G be an r-regular graph such that its Mycielskian graph AA(G) admits a distance magic labeling f .
Then dAA(G) .
i ) = 2r, dAA(G) .
i ) = r 1 and dAA(G) .
= n.
Also, the sum of the weight of all the vertices xi is w.
i ) = r and those of yi is f .
i ) r i ) = r i ) = kn i ) nf .
= kn.
From Equation .
and Equation .
, we obtain f .
i ) = nf .
O If we assign the smallest labels 1, 2, 3, .
, n to the vertices y1 , y2 , .
, yn , then we get f .
i ) and we know that f .
O 2n 1.
Using these inequalities in Equation .
, we get rn.
O n.
=Ne r O 4 Oe Since, n is at least 1, r O 3.
This completes the proof.
Thus, it is clear that if G is an r-regular graph such that the Mycielskian graph AA(G) admits a distance magic labeling, then r OO .
, 2, .
If G is 1-regular graph then (G) = 1.
Therefore, by Lemma 3.
AA(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 2Oeregular 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 K4 and by Corollary 3.
Mycielskian of K4 is not distance magic.
Lemma 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,3 and hence by Theorem 3.
Mycielskian of K3,3 is not distance magic.
For Mycielskian of graph G as shown in Figure 5.
, consider N .
= .
, d, f } and N .
= .
, d, .
Therefore.
NG .
nNG .
= .
, f } which implies |NG .
nNG .
| = 2 and by Lemma 3.
Mycielskian of this graph is not distance magic.
This proves the lemma.
Distance magic labelling of Mycielskian graphs .
K3,3 Pawar and T.
Singh .
G Figure 5.
3-regular graphs of order 6.
Lemma 3.
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 .
, denoted by G1 .
G2 .
G3 .
G4 .
G5 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 .
nN .
as follows:
In graph G1 .
N .
nN .
= .
, .
and hence |N .
nN .
| = 2.
In graph G2 .
N .
nN .
= .
, .
and hence |N .
nN .
| = 2.
In graph G3 .
N .
nN .
= .
, f } and hence |N .
nN .
| = 2.
In graph G4 .
N .
nN .
= .
, .
and hence |N .
nN .
| = 2.
In graph G5 .
N .
nN .
= .
, .
and hence |N .
nN .
| = 2.
Then by Lemma 3.
Mycielskian of a 3-regular graph of order 8 is not distance magic.
Theorem 3.
The Mycielskian of 3-regular graph G of order O 8 is not distance magic.
Proof.
Proof follows from Corollary 3.
Lemma 3.
3 and Lemma 3.
There are nineteen 3-regular graphs of order 10 .
We consider the Petersen graphAithe best-known graph in this family.
Theorem 3.
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 , y8 in AA(G) as shown in Figure 7 are:
Distance magic labelling of Mycielskian graphs .
G1 .
G3 Pawar and T.
Singh .
G2 .
G4 .
G5 Figure 6.
3-regular graphs of order 8.
NAA(G) .
1 ) = .
2 , x5 , x6 , .
NAA(G) .
4 ) = .
3 , x5 , x9 , .
NAA(G) .
7 ) = .
2 , x9 , x10 , .
NAA(G) .
8 ) = .
3 , x6 , x10 , .
Hence, their weights are given by, w.
1 ) = f .
2 ) f .
5 ) f .
6 ) f .
4 ) = f .
3 ) f .
5 ) f .
9 ) f .
7 ) = f .
2 ) f .
9 ) f .
10 ) f .
8 ) = f .
3 ) f .
6 ) f .
10 ) f .
Since, all weights are same, w.
1 ) = w.
7 ) gives f .
5 ) f .
6 ) = f .
9 ) f .
10 ) .
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh and w.
4 ) = w.
8 ) gives f .
5 ) f .
9 ) = f .
6 ) f .
10 ).
Subtracting Equation .
from Equation .
we obtain a contradiction f .
6 ) = f .
9 ).
Figure 7.
Petersen Graph.
Proposition 3.
Let G be a graph.
If AA(G) is a regular graph, then AA(G) is not distance magic.
Proof.
Let G be a graph on n vertices such that AA(G) is r-regular.
Then by Theorem 3.
G O
= K2 .
But AA(K2 ) = C5 and by Theorem 2.
C5 is not distance magic.
This completes the proof.
Observation 1.
The graph G and its Mycielskian AA(G) do not share the property of being distance magic, i.
AA(G) is distance magic irrespective of G, e.
, the path on 3 vertices P3 is distance magic .
but AAr (P3 ) is not distance magic for any r Ou 1 .
ee Corollary 3.
Whereas.
C4 is distance magic .
and AA(C4 ) is also distance magic .
ee Theorem 3.
but AA2 (C4 ) is not distance 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 AAr (G) is distance magic, for all r Ou 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/002.
Government of India, for providing financial support.
Also, authors are thankful to the referees for their invaluable comments.
Distance magic labelling of Mycielskian graphs Pawar and T.
Singh
References