![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Hefetz, Mütze, and Schwartz conjectured that every connected undirected graph admits an antimagic orientation (Hefetz et al., 2010). In this paper we support the analogous question for distance magic labeling. Let be an Abelian group of order
. A directed
-distance magic labeling of an oriented graph
of order
is a bijection
with the property that there is a magic constant
such that for every
In this paper we provide an infinite family of odd regular graphs possessing an orientable
-distance magic labeling. Our results refer to lexicographic product of graphs. We also present a family of odd regular graphs that are not orientable
-distance magic.
Keywords:
1 Introduction
Consider a simple graph and a simple oriented graph
. We denote by
the vertex set and by
the edge set of
. For
we denote by
the vertex set and by
the arc set of
. We denote the order of
by
. An arc
is considered to be directed from
to
, moreover
is called the
and
is called the
of the arc. For a vertex
, the set of head endpoints adjacent to
is denoted by
, and the set of tail endpoints adjacent to
is denoted by
. For graph theory notations and terminology not described in this paper, the readers are referred to Citation[1].
In this paper we investigate distance magic labelings, which belong to a large family of magic-type labelings. Probably the best known problem in the area of magic and antimagic labelings is the antimagic conjecture by Hartsfield and Ringel Citation[2], which claims that the edges of every graph except can be labeled by integers
so that the weight of each vertex is different. The conjecture is still open. Twenty years later Hefetz, Mütze, and Schwartz introduced the variation of antimagic labelings, i.e., antimagic labelings on directed graphs. Moreover, they conjectured that every connected undirected graph admits an antimagic orientation Citation[3]. The papers Citation[4–6] stated the analogous question for distance magic labeling, namely when a graph
of order
has a
-distance magic orientation.
Formally speaking, a directed -distance magic labeling of an oriented graph
of order
is a bijection
with the property that there is a magic constant
such that for every
where the sum is taken in the group
, and instead of writing
we use a
notation.
If for a graph there exists an orientation
such that there is a directed
-distance magic labeling
for
, we say that
is orientable
-distance magic and the directed
-distance magic labeling
we call an orientable
-distance magic labeling.
Cichacz, Freyberg and Froncek proved the following theorems.
Theorem 1
Citation[4] Let have order
and all vertices of odd degree. There does not exist an orientable
-distance magic labeling of
.
Theorem 2
Citation[4] The complete graph is orientable
-distance magic if and only if
is odd.
Theorem 3
Citation[4] Let be a complete
-partite graph such that
and
is odd. The graph
is orientable
-distance magic graph if
.
In this paper we consider two out of four standard graph products (see Citation[7]). The Cartesian product of graphs
and
is a graph such that the vertex set of
is the Cartesian product
and any two vertices
and
are adjacent in
if and only if either
and
is adjacent with
in
or
and
is adjacent with
in
.
The lexicographic product is a graph with the vertex set
. Two vertices
and
are adjacent in
if and only if either
is adjacent with
in
or
and
is adjacent to
in
.
is also called the composition of graphs
and
and denoted by
(see Citation[1]).
We will also discuss join graphs. We say that is a join graph if
is the complete union of two graphs
and
. In other words,
and
. If
is the join graph of
and
, we shall write
.
Freyberg and Keranen proved recently.
Theorem 4
Citation[6] If is an orientable
-distance magic graph of order
and
, then the lexicographic product
is orientable
-distance magic.
So far there was known only one example of odd regular graph orientable -distance magic Citation[4]. Note that by Theorems 2 and 4 for
odd and
the product
is orientable
-distance magic. In Theorem 6 we give necessary and sufficient conditions for
being orientable
-distance magic. As a consequence, we provide an infinite family of odd regular graphs possessing directed
-distance magic labeling. Moreover in Section 3 we will show one more example of a family of graphs that is orientable
-distance magic if and only if
. In the last section we present some family of odd regular graphs that are not orientable
-distance magic. Before we proceed, we will need the following theorem.
Theorem 5
Citation[8] Let be a partition of the positive integer
, where
for
. Let
. Then the set
can be partitioned into pairwise disjoint subsets
such that for every
,
with
.
2 Lexicographic products
Consider a graph . Let us denote independent sets of vertices by
where
for
. We give necessary and sufficient conditions for
being orientable
-distance magic.
Theorem 6
A graph is orientable
-distance magic if and only if
or
for
. When
,
is orientable
-distance magic if and only if
is odd.
Proof
By Theorem 2 we can assume that . If
is odd, then we are done by Theorem 3. Moreover from Theorem 1 we can conclude that for
and
there does not exist an orientable
-distance magic labeling for the graph
. We consider two cases:
Case 1: .
Let .
If , then let
and there exists a zero-sum partition
of the set
such that
for every
by Theorem 5. Let
be the index of subset containing
.
If , then by Theorem 5 there exists a partition of
into
such that
,
for
and
for
. Without loss of generality
, where
. Let
,
,
, where
.
Note that in both situations for
. Label vertices from each set
by the elements of
with the restriction that
and
.
Let be the orientation for the edge
. For edges
from
we have
(1)
(1) This way we obtained the edge orientation between
and
. For the remaining pairs of partition vertex sets
and
we demand all edges to be oriented the same from the
th set to the
th set or conversely. Let us check the weight of the vertex
for
. Namely
Consider now
and its weight
Now we calculate
for
.
And finally we check
, where
and
. Namely
Thus
is orientable
-distance magic.
Case 2: and
.
For the set we introduce the following orientation
for all
(where operations are taken modulo
). For the remaining edges we have
We say that precedes
and
succeeds
if arcs between vertices of
and
have tails in
and heads in
. Define the labeling
such that
, where
and
. It is easy to see that for each
we have
where
is a constant difference between labels
and
where
. Therefore
. We obtain the magic constant
. □
Observe that if is an odd regular graph, then the lexicographic product
is also an odd regular graph. From Theorem 5 we obtain the following observation showing that there exist infinitely many odd regular graphs that are orientable
-distance magic for a cyclic group
.
Observation 1
The lexicographic product has a
-distance magic labeling for any
.
Note that the method presented above works also for other families of graphs, for instance for . We just assign the label
to some vertex in the center of the
and place
in the other set. The orientation in
is similar to the general case.
3 Join graphs
Theorem 7
The join graph is orientable
-distance magic if and only if
.
Proof
Let be consecutive vertices belonging to
, and let
be the remaining vertex of
.
First we prove that when
is not orientable
-distance magic. We proceed by contradiction and assume that
is orientable
-distance magic. Let
be some orientable
-distance magic labeling of
and let
be the magic constant. Because the group
has an even order, it makes sense to speak about parity. Observe that
. Therefore the parity of
is always opposite to the parity of
.
Since we get
. Moreover
which implies
, and in general
for
, and
for
. On the other hand
, so
, but
. Contradiction. In other cases we show that
is orientable
-distance magic.
We set the following labeling. When is odd we assign
for
and
. Now we set orientation.
and
for
. And finally
.
Observe that when we get
. Next,
,
, and finally
. This way we obtain magic constant
.
When we change the orientation of two arcs:
to
and
to
, where
. We set the same labeling as in the previous case. Therefore
, where
, can be calculated similarly. Next,
, and
And we get the magic labeling with
. □
4 Prism graphs
In this section we present some odd regular graphs that are not orientable distance magic. The prism is a Cartesian product .
Theorem 8
Let us consider a prism graph of order
. There does not exist an orientable
-distance magic labeling.
Proof
If the thesis is fulfilled on the basis of Theorem 1. We are going to consider situation when
. Suppose that there exists an oriented
-distance magic labeling for a graph
. Since
is bipartite graph we can assume that it has partition sets
and
.
As in Section 3 since has an even order, it makes sense to speak about even and odd elements. Let us focus on the parity of the magic constant. There is no need to consider direction of edges because addition and subtraction modulo
give the same results. If we know the parity of three consecutive labels
,
, then we can say what is the parity of the element
. The parity of the magic constant generated by three consecutive labels needs to be preserved, which means:
Therefore,
for any
.
Hence knowing the parity of three initial labels one can establish parity of the remaining labels. We examine two possibilities, according to the cardinality of .
Suppose first, that . One can check that
for any
from the same partition set. Thus,
for
and
. Because the graph is odd regular the parity of the magic constant depends on the partition set, a contradiction.
We assume now that , then we have to examine every three initial labels generating the rest of the sequence. For labels of the same parity we have contradiction that is compatible with the description above. If one of the three initial
is an even number and the rest are odd numbers then in the whole
component we have
of all even numbers and
of odd numbers. They generate even magic constant. On the other hand, in
component we have
of all odd numbers and
of all even numbers (the rest of remaining labels). This does not allow a labeling that generates even magic constant because vertices from
also should meet the rule of the same parity on every third element of the sequence. Therefore, there also should be
of all even numbers and
of odd numbers or all labels were even. That situation is not possible.
The case looks similar in the scheme with one odd number and two even numbers in initial three . Above consideration exhausts other possible cases and therefore proves the rightness of the formula. □
So far there was known only one example of a graph that is orientable -distance magic Citation[4], in this paper we have introduced an infinite family of odd regular graphs possessing an orientable
-distance magic labeling. We have also provided a family of join graphs that are orientable
-distance magic. Moreover we presented a family of odd regular graphs that are not orientable
-distance magic. One may wonder whether there are more infinite families of lexicographic product of graphs being orientable
-distance magic. The same question could be posed for join graphs. We still have a little knowledge in this field. We hope our results and proof techniques will be useful in further research in graph labeling.
Acknowledgments
We would like to thank Sylwia Cichacz for her support, encouragement, assistance in proofreading this researchand delivering valuable tips and resources. We could not have imagined having a better advisor and mentor. We are also very grateful to Dominika Datoń, Kinga Patera, Natalia Pondel, Maciej Gabryś and Przemysław Zietek from “Snark” Research Student Association for their help and involvement in initial phase of our analysis.
References
- HararyF., Graph Theory1994Addison-WesleyReading22
- HartsfieldN.RingelG., Pearls in Graph Theory1990Academic PressBoston
- HefetzD.MützeT.SchwartzJ., On antimagic directed graphs J. Graph Theory 64 3 2010 219–232
- CichaczS.FreybergB.FroncekD., Orientable Zn-distance magic graphs Discuss. Math. Graph Theory 392019 533–546
- FreybergB.KeranenM., Orientable Zn-distance magic labeling of Cartesian products of two cycles Australas. J. Combin. 69 2 2017 222–235
- FreybergB.KeranenM., Orientable Zn-distance magic graphs via products Australas. J. Combin. 70 3 2018 319–328
- HammackR.ImrichW.KlavžarS., Handbook of Product Graphssecond ed.2011CRC PressBoca Raton, FL
- ZengX., On zero-sum partitions of abelian groups Integers 152015Paper No. A44, 16 pp.