# On the Barycentric Labeling of Certain Graphs

Authors: Saeid Alikhani; Zeynab Amirzadeh
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

LetA be an abelian group. A graph G is called A-magic if there exists edge labeling l
:
E
(
G
)
→
A
∖
{
0
} such that the induced vertex set labeling l
+
:
V
(
G
)
→
A, defined by l
+
(
v
)
=
∑
u
v
∈
E
(
G
)
‍
l
(
u
v
), where the sum is over all edges in E
(
G
), is a constant map. A graph G is A-barycentric-magic (or has A-barycentric labeling) if G is A-magic and also satisfies l
+
(
v
)
=
deg
(
v
)
l
(
u
v
v
) for all v
∈
V and for some vertex u
v adjacent to v. In this paper we consider some graphs G and characterize all m
∈
N for which G is Z
m-barycentric-magic.


---

## Body

## 1. Introduction

LetG
=
(
V
,
E
) be a finite, simple, and undirected graph. Labeling for a graph is a map that takes graph elements to numbers (usually positive or nonnegative integers). Let A be an abelian group (written additively). The graph G is called A-magic if there exists labeling l
:
E
(
G
)
→
A
∖
{
0
} such that, for each vertex v, the sum of values of all edges incident with v, denoted by l
+
(
v
), is a constant; that is, l
+
(
v
)
=
c, for some c
∈
A. When this constant is 0, G is said to be A-zero-sum magic. The integer-magic spectrum of a graph G is the set IM
(
G
)
=
{
k
∈
N
:
G
is
Z
k
-magic
}.As an example, Figure1 shows a graph which is A-zero sum magic, for every group A (see [1]).Figure 1
An example forA-zero sum magic graph.Let us state some easy lemmas (or observations). They are straightforward to verify and can be found in [2].Lemma 1.
A graphG is Z
2-magic if and only if every vertex of G is of the same parity.Lemma 2.
An Eulerian graphG with even size is A-magic.Lemma 3.
IfA
1 is a subgroup of A and graph G is A
1-magic, then G is A-magic.Various authors have introduced labeling that generalizes the idea of magic square. Kotzig and Rosa [3] defined a magic labeling to be total labeling on the vertices and edges in which the labels are the integers from 1 to |
V
(
G
)
|
+
|
E
(
G
)
|. The sum of labels on an edge and its two endpoints is constant. In 1996 Ringel and Llado [4] redefined this type of labeling as edge-magic. Also, Enomoto et al. [5] have introduced the name super edge-magic for magic labeling in the sense of Kotzig and Rosa, with the added property that the n vertices receive the smaller labels, {
1,2
,
…
,
n
}. Lee et al. [6] defined the concept of k-edge magic graphs and studied it for certain graphs (see, e.g., [7]). Recently authors in [8] defined a new kind of group magicness graphs.Here we recall the following definition.Definition 4 (see [8]).
If there exists labelingl for a graph G, whose induced vertex set labeling is a constant map and for all v
∈
V
(
G
) the sum l
+
(
v
) also satisfies l
+
(
v
)
=
deg
⁡
(
v
)
l
(
u
v
v
) for some vertex u
v adjacent to v
,
G is said to be A-barycentric-magic.Note that the motivation of Definition4 is the following definition of k-barycentric sequence which was introduced in [9] and has already been used in graph labeling problems, specially in Ramsey theory [9–11].Definition 5.
Letx
1
,
x
2
,
…
,
x
k be k elements of an abelian group A. This sequence is k-barycentric if there exists j such that x
1
+
x
2
+
⋯
+
x
j
+
⋯
+
x
k
=
k
x
j. The element x
j is called a barycenter.Example 6.
Figure2 shows a graph G with |
V
|
=
8 and |
E
|
=
9 which is Z
4-barycentric-magic. Note that in this example the sum l
+
(
v
) is 2 (mod 4) for all v
∈
V
(
G
).Figure 2
Z
4-barycentric magic graph.The study of the barycentric-magic graphs is motivated by the relationship between different types of magic labeling and the behavior of the sums of sequences in abelian groups. That is,A-magic labeling of a graph G is equivalent to sequences of nonzero elements of A with the same sum; A-zero-sum magic labeling is equivalent to zero-sum sequences in A
∖
{
0
}.Note thatA-barycentric-magic labeling is equivalent to sequences of nonzero elements of A that contain one element which is the “average” of its terms, called barycentric sequence.Similar to the definition of integer magic spectrum ofA-magic graphs we state the definition of barycenter-magic spectrum of graph.Definition 7 (see [8]).
For a given graphG the set of all positive integers m for which G is Z
m-barycentric-magic is called the barycenter-magic spectrum of G and is denoted by BMS
(
G
).In this paper, we consider specific graphsG and characterize all m
∈
N for which G is Z
m-barycentric-magic.


## 2. Barycentric-Magic Labeling of Certain Graphs

In this section, we characterize allm
∈
N for which G is Z
m-barycentric-magic. First we consider some complete bipartite graphs.First we state the following theorem.Theorem 8 (see [8]).
The complete bipartite graphK
2,3 is not Z
m-barycentric-magic for any m.We generalize the previous theorem.Theorem 9.
Forn
≥
3, K
2
,
n is Z
m-barycentric-magic if and only if g
c
d
(
n
-
2
,
m
)
≠
1.Proof.
LetV
(
K
2
,
n
)
=
{
u
1
,
u
2
}
∪
{
v
1
,
v
2
,
…
,
v
n
} be the set of vertices of K
2
,
n. For each j, the edges incidents to v
j must have the same label. Suppose that l
(
u
1
,
v
j
)
=
α
j and l
(
u
2
,
v
j
)
=
α
j. Then 2
α
1
≡
2
α
2
≡
⋯
2
α
n (mod m). We consider the two following cases.
Case  1  (
m
is odd). In this case, the condition 2
α
1
≡
2
α
2
≡
⋯
2
α
n(mod m) implies that all edges have the same label, say α. By the condition l
+
(
u
i
)
=
l
+
(
v
j
) we have (
n
-
2
)
α
≡
0(mod m) and this is impossible when gcd
(
n
-
2
,
m
)
=
1. If gcd
(
n
-
2
,
m
)
=
d
≠
1, then using α
=
m
/
d gives a barycentric-magic labeling.
Case  2  (
m
is even). Here we give two different approaches. In this case, the condition 2
α
1
≡
2
α
2
≡
⋯
2
α
n (mod m) implies that there are at most two different labels α and β
=
α
+
m
/
2, such that 2
α
≡
2
β (mod m). Now label K
2
,
n as follows: l
(
u
1
,
v
j
)
=
α for 1
≤
j
≤
k and l
(
u
1
,
v
j
)
=
β for k
+
1
≤
j
≤
n, for some 1
≤
k
≤
n. Then, the edges incidents to u
2 must be labeled in the same way. This labeling is barycentric-magic if and only if
(1)
k
α
+
(
n
-
k
)
β
≡
n
α
≡
2
α
≡
2
β
(
mod
⁡
m
)
or
(2)
k
α
+
(
n
-
k
)
β
≡
n
β
≡
2
α
≡
2
β
(
mod
⁡
m
)
.
Without loss of generality, we consider only the first relation. The condition n
α
≡
2
α(mod m) is satisfied only when gcd
(
n
-
2
,
m
)
≠
1. So suppose that gcd
(
n
-
2
,
m
)
=
d
≠
1. Choose k
=
d
,
α
=
m
/
d, and β
=
α
+
m
/
2 and since n
-
d is even we get
(3)
k
α
+
n
-
k
β
≡
n
α
mod
⁡
m
,
n
α
≡
2
β
≡
2
α
(
mod
⁡
m
)
.
Therefore with this labeling K
2
,
n is Z
m-barycentric-magic.
Now we state the second approach.
Sincen
α
=
2
α(mod m), if gcd
(
m
,
n
-
2
)
=
1, then α
=
0, a contradiction. Conversely, let α
1
=
α
2
=
⋯
=
α
k
=
m
/
d. This is also a Z
m-barycentric-magic labeling for K
2
,
n.Example 10.
Consider the graphK
2,10 and the group Z
10. Let V
(
K
2,10
)
=
{
u
1
,
u
2
}
∪
{
v
1
,
v
2
,
…
,
v
10
} be the set of vertices of K
2,10. In this case, since d
=
gcd
(
n
-
2
,
m
)
=
2 choose α
=
m
/
d
=
5 and β
=
α
+
m
/
2
=
10 and k
=
d
=
2. The labeling of K
2,10 is as follows:l
(
u
i
v
j
)
=
5 for i
=
1,2 and j
=
1,2;
l
(
u
i
v
j
)
=
10 for i
=
1,2 and j
=
3
,
…
,
10;
thenl
+
(
v
j
)
=
2
×
5
=
deg
⁡
(
v
j
)
×
5
≡
10 (mod 10) for j
=
1,2;
l
+
(
v
j
)
=
2
×
10
=
deg
⁡
(
v
j
)
×
10
≡
10 (mod 10) for j
=
3
,
…
,
10;
l
+
(
u
i
)
=
2
×
5
+
8
×
10
≡
10
≡
deg
⁡
(
u
i
)
×
5 (mod 10) for i
=
1,2. Then with this labeling we get barycentric-magic labeling.Here we consider friendship graphs.Letn be any positive integer and F
n Dutch-Windmill, or friendship graph with 2
n
+
1 vertices and 3
n edges. In other words, the friendship graph F
n is a graph that can be constructed by coalescence n copies of the cycle graph C
3 of length 3 with a common vertex. The friendship theorem of Erdös et al. [12] states that graphs with the property that every two vertices have exactly one neighbour in common are exactly the friendship graphs. Figure 3 shows some examples of friendship graphs.Figure 3
Friendship graphsF
2
,
F
3
,
F
4, and F
n, respectively.Theorem 11.
Friendship graphsF
n are Z
2
m-barycentric-magic graphs for any m
∈
N.Proof.
Consider friendship graphF
n and suppose that deg
⁡
(
v
)
=
2
n and deg
⁡
(
u
i
)
=
2 for i
=
1
,
…
,
n. We label all the edges of F
n with α
∈
Z
2
m
∖
{
0
}. Since 2
n
α
≡
2
α (mod 2
m) (e.g., put m
=
α), the graphs F
n are Z
2
n-barycentric-magic.Here we consider another families of graphs denoted byH
2
n (see Figure 4).Figure 4
GraphH
2
n.Theorem 12.
The graphsH
2
n are not Z
k-barycentric-magic for every k.Proof.
Suppose that the set of vertices ofH
2
n is V
=
{
u
1
i
,
u
2
i
}
∪
{
w
1
,
w
2
}
∪
{
v
j
}, where i
=
1
,
…
,
n
/
2 and j
=
1
,
…
,
n
-
2 and deg
⁡
(
u
1
i
)
=
deg
⁡
(
u
2
i
)
=
2, deg
⁡
(
w
1
)
=
deg
⁡
(
w
2
)
=
3, and deg
⁡
(
v
j
)
=
4. One can consider some cases to prove that there is no Z
k barycentric-magic labeling for H
2
n. Here we state two cases. We label the graph H
2
n as follows.
Case  1. Label all edges of H
2
n with α
∈
Z
k
∖
{
0
}. In this case 3
α
≡
2
α (mod k) or α
≡
0(mod k) which is not true.
Case  2. We label H
2
n as follows: l
(
w
1
u
11
)
=
l
(
v
j
u
1
i
)
=
l
(
w
2
u
1
(
n
/
2
)
)
=
α
+
r for each i
=
1
,
…
,
n
/
2 and l
(
w
1
v
1
)
=
l
(
v
2
j
v
2
j
+
1
)
=
l
(
w
2
v
n
-
2
)
=
α for each j
=
1
,
…
,
n
-
3 and l
(
v
2
j
-
1
v
2
j
)
=
α
+
3
r for each j
=
1
,
…
,
n
-
3 and l
(
w
1
u
21
)
=
l
(
v
j
u
2
i
)
=
l
(
w
2
u
2
n
/
2
)
=
α
+
2
r
(
i
=
1
,
…
,
n
/
2 and j
=
1
,
…
,
n
-
2). From l
+
(
w
1
)
=
l
+
(
u
11
) we have 3
α
+
3
r
≡
2
α
+
2
r (mod k) or α
+
r
≡
0 (mod
⁡
k), but α
+
r is the label of edges u
1
i
v
j, so this labeling is not barycentric-magic.



---

*Source: 482635-2014-11-16.xml*