![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be an additive abelian group of order
and let
be a partition of
where
A constant sum partition (or
-sum partition) of
is a pairwise disjoint union of subsets
such that
and
for some fixed
and every
In 2009, Kaplan, Lev, and Roditty proved that a 0-sum partition of the cyclic group
exists for
odd if and only if
In this paper, we address the case when
is even. In particular, we show that a
-sum partition of
exists for
even and
odd if and only if
Moreover, we provide applications to distance magic-type graphs including the classification of
-distance magic complete
-partite graphs for
odd.
1 Constant sum partitions
Let be a partition of the positive integer
, where
. Let
be an additive abelian group of order
and
. A constant sum partition (or
-sum partition) of
is a pairwise disjoint union of subsets
such that
,
, and
, for every
. If such a partition of
can be found for every partition of
with
, we say that
has the constant sum property,
. If
has the
property and
, then we say
has the
property. Kaplan et al. proved the following in Citation[1].
Theorem 1
Citation[1] The cyclic group has the
property if and only if
is odd.
In this paper, we focus on constant sum partitions of the cyclic group of even order. We begin with a necessary condition.
Observation 2
Let be a partition of the integer
. If
is even and a
-sum partition of
exists, then
.
Proof
Since a -sum partition of
exists,
.□
Because the constant sum partition of any group is trivial when , we will assume
from now on. From Observation 2, we obtain the following corollaries. Proofs of the corollaries are left to the reader.
Corollary 3
Let be a partition of the integer
. If
and there exists a
-sum partition of
, then both
and
are odd.
Corollary 4
Let be a partition of the integer
. If
and there exists a
-partition of
, then
.
Our next result identifies necessary and sufficient conditions for the existence of a constant sum partition of the cyclic group for an even integer with an odd number of parts. Let be a set of integers. For any subset
of
, we say
is a
-sum subset of
if the sum of all the elements in
is
. We denote by
the set
.
Theorem 5
If is even and
is odd, then
has the
property.
Proof
Let with
, and
. We will prove the theorem by partitioning
into pairwise disjoint subsets
such that
and
, for every
. The necessity of
is obvious. Relabel indices so that
with
,
, where
is even for
and odd for
. The assumption of
even and
odd implies
is even and
is odd.
Observe that since every element in can be written as
for a unique
, it suffices to partition the set
into
0-sum subsets of size 3,
-sum subsets of size 2, and
0-sum subsets of size 2, all pairwise disjoint.
First we construct the -sum subsets of size 2. Let
and
for
.
If and
, construct the
-sum subsets of size 3 as follows. Let
Whereas if and
, let
In either case, let for
. These sets are pairwise disjoint as long as
(from the
),
and
(from the
’s). All three inequalities are satisfied by assumption since
. Also, notice the integer
if and only if
, and the integer
if and only if
. Therefore, the
remaining elements in
may be partitioned into
pairwise disjoint 0-sum pairs, completing the desired partition of
. Place these 0-sum pairs arbitrarily into
sets (keeping the 0-sum pairs together)
so that
for
and if
, then
and
for
. Whereas if
, then
for
and
.
If , let
If
, let
In both cases, we have partitioned into pairwise disjoint subsets
such that
and
, for every
, proving the theorem.□
Example 6
Find a constant sum partition of for the partition
.
We have ,
, and
. The partition of
is
The corresponding constant sum partition of
is
Replacing the integer
in
with
, we obtain a 21-sum partition of
. □
One may wonder what can be said of the existence of constant sum partitions of the cyclic group for even integers having an even number of parts. If all partite sets are the same size, the following can be said.
Theorem 7
Let be a partition of the positive integer
. If
is even, then
can be partitioned into pairwise disjoint subsets
such that
and
, for every
.
Proof
Define disjoint -sum pairs
for
. Let
for
. Since
and
for every
, we have proved the theorem.□
2 Distance magic-type graphs
Let be a simple graph with
. Let
be a bijection and for all
, define the weight of the vertex as
. If
for some number
and all
, we say
is a distance magic labeling of
(with magic constant
) and call
a distance magic graph.
If instead of using integers as labels group elements are used, then the following generalization of distance magic labeling is possible. Let be an additive abelian group of order
and let
be a bijection. If there exists
such that
for all
, we say
is a
-distance magic labeling of
and call
a
-distance magic graph.
A further generalization to directed graphs is possible as follows. Let be a directed graph and let
be a bijection. Define the weight of a vertex,
, for all
. If
for some
and all
, we say
is a directed
-distance magic labeling of
and call the underlying simple graph
an orientable
-distance magic graph.
shows side-by-side labelings of each of the three magic-type labelings of the 4-cycle, .
3 Complete ![](//:0)
-partite graphs
It is an easy observation that the complete -partite graph is not
-distance magic when
. The next theorem completely classifies
-distance magic labelings of complete bipartite graphs Citation[2], complete tripartite graphs Citation[3], and complete
-partite graphs for
odd Citation[2].
Theorem 8
Citation[2,3] Let be a complete
-partite graph with
, and
. If
, the graph
is
-distance magic if and only if
. If
,
is
-distance magic if and only if
. If
is odd,
is
-distance magic if and only if
.
The following three theorems apply our results from Section 1.
Theorem 9
Let be a complete
-partite graph such that
is odd,
, and
is even. The graph
is
-distance magic if and only if
.
Proof
Let with vertex set
. Denote each independent set of vertices
so that
and identify the
th vertex in
by
.
Suppose first that . Partition the elements of
into pairwise disjoint subsets
such that
and
for every
. Such a partition exists by Theorem 5. Define
so that
is an arbitrary bijection for
. The weight of any vertex
is
Therefore,
is a
-distance magic labeling and
is
-distance magic.
Suppose on the other hand that is
-distance magic with (bijective) labeling
. If
, then
and
, which implies
. But this contradicts the bijective property of
. Therefore,
.□
Combined with Theorem 8, we have completed the classification of -distance magic labelings of complete odd-partite graphs.
Theorem 10
Let be a complete
-partite graph such that
is odd,
, and
. The graph
is
-distance magic if and only if
.
Proof
The proof is by Theorems 8 and 9.□
Next we turn our attention to complete even-partite graphs.
Theorem 11
Let where
is even and
. The complete
-partite graph
is
-distance magic.
Proof
The proof follows from Theorem 7 in a similar way as Theorem 9 followed from Theorem 5, so we omit the details.□
4 Directed complete ![](//:0)
-partite graphs
For directed graphs, the orientable -distance magic classification of complete
-partite graphs is finished only for
as the following theorem shows Citation[4].
Theorem 12
Citation[4] Let be a complete
-partite graph with
, and
. If
,
is orientable
-distance magic if and only if
is odd. If
,
is orientable
-distance magic if and only if
. If
,
is orientable
-distance magic for all
.
The authors of Citation[4] cited Citation[1] to obtain the following observation regarding complete -partite graphs of odd order.
Observation 13
Citation[4] Let be a complete
-partite graph with
, and
, an odd number. If
, then
is orientable
-distance magic.
From Theorem 5, we obtain the following new result.
Theorem 14
Let be a complete
-partite graph with
, and
. If
is odd and
, then
is orientable
-distance magic.
Proof
Let with vertex set
. Denote each independent set of vertices
so that
and identify the
th vertex in
by
. If
is odd,
is orientable
-distance magic by Observation 13, so we may assume from now on that
is even.
Construct a -distance magic labeling of
using Theorem 9. Orient the edges of
as follows. Let
with vertex set
. Notice that since
is odd,
is Eulerian. Form the directed graph
by orienting the edges of
to form a flow (all arcs are joined head to tail) along the Eulerian cycle. Necessarily, every vertex
is adjacent to exactly
heads of arcs and exactly
tails of arcs. Now construct the directed graph
by orienting the edges of
so that the edge
receives the same orientation as the corresponding edge
in
.
The weight of any vertex is now
Therefore,
is an orientable
-distance magic labeling, and
is orientable
-distance magic.□
We complete this section by applying Theorem 7 to directed graphs.
Theorem 15
Let be a complete
-partite graph and
. If
is even and
is odd, then
is orientable
-distance magic.
Proof
The proof follows from the -distance magic labeling given in Theorem 11 and arguments similar to those in the proof of the previous theorem.□
5 Conclusion
We have considered the following question. Given a positive integer , for which partitions of
is it possible to partition the cyclic group
into
pairwise disjoint subsets
such that
, and
, for some fixed element
and every
Table 1 summarizes for which (feasible) pairs
we now have a complete answer. The cells shaded gray in the table reflect non-existence results and the cells that contain a “?” reflect open cases.
References
- KaplanG.LevA.RodittyY., On zero-sum partitions and anti-magic trees Discrete Math. 3092009 2010–2014
- CichaczS., Note on group distance magic complete bipartite graphs Central Eur. J. Math. 12 3 2014 529–533
- CichaczS., On zero sum-partition of Abelian groups into three sets and group distance magic labeling Ars Math. Contemp. 13 2 2017 417–425
- CichaczS.FreybergB.FroncekD., Orientable Zn-distance magic graphs Discuss. Math. Graph Theory. 39 2 2019 533–546