![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be a simple undirected graph and let A be an additive Abelian group with identity 0. A mapping
is said to be a A-vertex magic labeling of G if there exists a μ in A such that
for any vertex v of G. If G admits such a labeling, then it is called an A-vertex magic graph. If G is A-vertex magic for any non-trivial Abelian group A, then G is called a group vertex magic graph. In this paper, we consider A-vertex magic and group vertex magic labeling of different products of graphs.
1. Introduction
The concept of group vertex magic graphs was motivated by the V4 magic labeling for edges, which was introduced by Lee [Citation5] and it was proved that “A tree T is V4-magic if and only if all its vertices have odd degrees”. Here, V4 denotes the famous Klein’s four group. Low and Lee [Citation6] extended the study of V4-magic labeling for the product graphs by considering an arbitrary Abelian group instead of V4. By getting motivated by this concept, analogously the concept of group vertex magic graphs was introduced and studied in [Citation3]. Also, in [Citation3], the authors have obtained a characterization of all A-vertex magic trees of diameter up to 4, where the group A is V4. In [Citation4], Kollaran et al. have characterized the trees of diameter 5, which are V4 vertex magic. In this paper, we use group elements to label the vertices of a graph and we have extended the study of group vertex magicness of a graph by considering an arbitrary Abelian group. It is interesting to use the ideas of algebraic structure in graph theory. Here, we focus on group vertex magicness of join and tensor product of graphs, and we carefully use the remarkable theorems from group theory, namely Cauchy’s theorem, Sylow’s first theorem and fundamental theorem of finite Abelian groups in a fruitful way.
All graphs considered in this paper are simple finite graphs, and A denotes an Abelian group, not necessarily finite. For a graph G, we use V(G) (or simply V) for the vertex set of G. The open neighbourhood N(v) of a vertex v is the set of all vertices adjacent to v in G. For basic graph-theoretic ideas, we refer to Bondy and Murty [Citation1]. Let R be a commutative ring with unity, we denote the multiplicative group of all units in R by U(R). For concepts in group theory, we refer to Herstein [Citation2].
2. Main results
In this section we discuss the A-vertex magicness of join of two graphs.
Definition 1.
[Citation3] A mapping is said to be a A-vertex magic labeling of G if there exist a μ in A such that
for any vertex v of G. The element μ is called the magic constant of the labeling l. A graph G that admits such a labeling is called an A-vertex magic graph. If G is A-vertex magic graph for any non-trivial Abelian group A, then G is called a group vertex magic graph.
Theorem 1.
A graph G is -vertex magic for all primes p if and only if G is A-vertex magic for all finite Abelian groups A.
Proof.
Let A be any non-trivial Abelian group. Assume that G is -vertex magic, for all primes p. By Cauchy’s theorem, A has a subgroup isomorphic to
for some prime number p. Hence G is A-vertex magic for all finite Abelian groups A. The converse part is trivial. □
Observation 1.
A graph G is magic if and only if degree of every vertex in G is of same parity.
We prove the following theorem which is analogous to Lemma 1 in [Citation7].
Theorem 2.
Let l be a A-vertex magic labeling of a graph G. Then
where n is the number of vertices of G and μ is the magic constant.
Proof.
For each vertex we have
Clearly,
This sum counts the label of v exactly deg(v) times. Thus, the equation holds. □
The following theorem is a generalisation of Theorem and
in [Citation3].
Theorem 3.
Let be a complete k-partite graph. Then G is A-vertex magic, where
Proof.
Let be a partition of V(G) with
Let
where
Case 1.
p divides o(A), where p is an odd prime.
By Cauchy’s theorem, A has an element a of order p. If nj is odd, then define by
If nj is even, then define
Thus for all
Case 2.
4 divides o(A).
By Sylow’s first theorem and fundamental theorem of finite Abelian groups, A has a subgroup isomorphic to either or V4. Suppose A has a subgroup isomorphic to
If nj is odd, then
If nj is even, then
where o(a) = 4. Then
for all
Suppose A has a subgroup isomorphic to If nj is odd, then
for all i. If nj is even, then
Thus for all
Case 3.
A is an infinite Abelian group.
In this case, either A contains an element of finite order or A contains a subgroup isomorphic to Hence, the labeling defined in Case 1 or Case 2 is a magic labeling. □
Corollary 1.
Let be a complete k-partite graph with each partite size of same parity. Then G is group vertex magic.
Proof.
By Observation 1 and Theorem 3, we get the required result. □
The above corollary is a generalization of Theorem in [Citation3].
Theorem 4.
Let G1 and G2 be graphs. If the graph is A-vertex magic, then G1 and G2 are A-vertex magic.
Proof.
Let us assume that is A-vertex magic and the corresponding magic labeling is l. Now, define
by
Let
Since
in
we have
Since v1 and v2 are arbitrary vertices in G1, it follows that G1 is A-vertex magic. By a similar argument, we get G2 is A-vertex magic. □
Theorem 5.
Let G be an arbitrary r-regular graph with n vertices. Then the graph is A-vertex magic, where
Proof.
Let and
Let
or
where t is an odd prime or t = 4.
Case 1.
ra = na
Assume that ra = na = e. If and A has a subgroup isomorphic to
then define
by
for all i, where o(a) = t and if m is odd, then
If m is even, then
Thus, for all
If and A has a subgroup isomorphic to
then define
by
for all i and if m is odd, then
If m is even, then Thus
for all
Case 2.
Since let
Suppose
Now, define
by
for all i and if m is odd, then
If m is even, then
where
in
Thus
for all
Suppose Assume that
where
Let
and
Define
by
for all i and if m is even, then
If m is odd, then for all j. Thus, w(v) = na, for all
Case 3.
A is an infinite Abelian group.
In this case, either A contains an element of finite order or A contains a subgroup isomorphic to Z. Hence, the labeling defined in Case 1 or Case 2 is a magic labeling. □
A simple calculation gives following.
Proposition 1.
Let G be any graph and If l is an A-vertex magic labeling of
, then
, where
Theorem 6.
The graph is A-vertex magic, where
if and only if
n = 3 or
n = 4 or
, where
Proof.
Let be a partition of the vertex set of G, where
and
Assume that G is A-vertex magic. Let
not necessarily distinct. Now,
for all
For any i, j,
which implies
Therefore, l takes fixed value on
Case 1.
n is odd and
In this case by Proposition 1, we have Assume that
and
for all i, j. Then
and
for all i, j, which implies
In the group
we have b = 0, which is a contradiction.
Case 2.
n is even and From Proposition 1, it is enough to label
and v4 as follows
and for all
Then
and
which implies
In the group
we have
which is a contradiction.
Case 3.
and
In this case by Proposition 1, we have and
Now, it follows that
and
(say).
where
and
Since
we have
By prime factorization,
where
are odd prime, for all
In the group
we have c = 0, where
which is a contradiction.
Now, let us prove the converse part.
Case 1.
Assume that n = 3. Then the graph is regular. Therefore, the graph
is A-vertex magic graph.
Case 2.
Assume that n = 4. Define by
and for all
where
Hence
for all
Case 3.
Assume that and
If p is an odd prime and it divides o(A), then by Cauchy’s theorem A has an element a of order p. Define by
Hence, for all
If 4 divides o(A), then by Sylow’s first theorem and fundamental theorem of finite Abelian groups, A has a subgroup isomorphic to either or V4. If A has a subgroup isomorphic to
then define
by
and
for all
where o(a) = 4. Then
and
clearly
for all i, j. If A has a subgroup isomorphic to
then define
by
and for all
Then w(v) = mc, for all
□
Proposition 2.
Let G be a graph. If is A-vertex magic, where
then
Proof.
Let Assume that
is A-vertex magic and n > 3. Since
which implies
which is a contradiction. □
Theorem 7.
The graph is A-vertex magic, where
if and only if
Proof.
Let and
The necessity follows from Proposition 2. Now, let us prove the sufficiency.
Case 1.
n = 3.
Define by
for all
and
where
and
Then
for all
Case 2.
n = 2.
In this case the graph is regular and hence it is A-vertex magic. □
Theorem 8.
The graph is A-vertex magic, where
if and only if
Proof.
Let and
The necessity follows from Proposition 2. Now, let us prove the sufficiency. Let
and
Case 1.
n = 3.
Suppose m is odd. Define by
and
Thus
for all
Suppose m is even. Define by
and
An A-vertex magic labeling of
is given in .
Thus for all
Case 2.
n = 2.
Suppose m is odd. Define by
and
for all i. Thus
for all
Suppose m is even. Define by
for all i. Thus
for all
□
Theorem 9.
The graph is A-vertex magic, where
if and only if
and
m = 3 or
m = 4 or
, where
Proof.
Let and
Assume that G is A-vertex magic. Let
where
and not necessary distinct. By Proposition 2, we have
Suppose n = 2, then by Theorem 6, we get the required result.
Assume that n = 3.
Case 1.
m is odd, m > 3.
In this case by Proposition 1, we have Assume that
and
Then
and
which implies,
In the group
we have
which is a contradiction.
Case 2.
m is even and From Proposition 1, it is enough to label
and u4 as follows
and
Then
and
Since
which implies
In the group
we have
which is contradiction.
Case 3.
and
In this case by Proposition 1, we have and
Assume that
and
where
and
Since
we have
By prime factorization,
where pi’s are odd prime, for all
In the group
we have
where
which is a contradiction.
To prove converse part, assume that n = 2, then by Theorem 6, we get the required result.
Now, assume that n = 3.
Case 1.
m = 3
Then by Theorem 7, we get the required result.
Case 2.
m = 4
Define by
and
where
Thus
for all
An A-vertex magic labeling of
is given in .
Case 3.
and
If p is an odd prime and it divides o(A), then define by
for all j,
and
where o(a) = p and
Then
for all
If 4 divides o(A), then A has a subgroup isomorphic to either or V4. If A has a subgroup isomorphic to
then define
by
and
where o(a) = 4. Thus
for all
If A has a subgroup isomorphic to
then define
by
and
Thus w(v) = 0, for all
□
3. Group vertex magic labeling of product of graphs
In this section, we deal with tensor and lexicographic product of graphs which are group vertex magic.
Definition 2.
[Citation6, Citation8] The tensor product of graphs G and H is a graph such that the vertex set of
is the product
and vertices (g, h) and
are adjacent in
if and only if g is adjacent to
in G and h is adjacent to
in H.
Also, one can find several graph products in [Citation8].
Theorem 10.
Let A be an Abelian group, underlying a commutative ring R. If there exist A-vertex magic labelings and
for graphs G1 and G2 respectively, then
is A-vertex magic.
Proof.
Let us assume that the magic constant of G1 under the labeling l1 is a and the magic constant of G2 under the labeling l2 is b. Let and
Define
by
Assume that
and
Then
and
Now,
Since (u, v) is arbitrary, for all
□
Theorem 11.
The graph is A-vertex magic, where
and m > 1 if and only if
n = 2 or
n = 3.
Proof.
Let where
Assume that
and
is A-vertex magic. Since
which implies
That is, sum of any m – 1 distinct elements of
equal to 0, which implies
Therefore, the graph
is not
vertex magic, where p is prime and
Conversely, assume that n = 2. In this case the graph is regular and hence A-vertex magic.
Now, assume that n = 3. If p is an odd prime and it divides o(A), then define by
where o(a) = p. Thus
for all i, j. A
-vertex magic labeling of
where p is an odd prime is given in .
Suppose not, then 4 divides o(A). If A has a subgroup isomorphic to then define
by
where o(a) = 4. Thus
for all i, j.
If A has a subgroup isomorphic to then define
by
Thus for all i, j. □
Theorem 12.
The graph is A-vertex magic, when
if and only if
Proof.
Let where
Assume that
or
and
is A-vertex magic. Without loss of generality, assume that
Now, consider the path
Since
which implies
which is clearly not possible.
Conversely,
Case 1.
n = 2.
Suppose that m = 2. Then the graph is regular and hence A-vertex magic. Suppose that m = 3. Define
by
and Thus
for all
Case 2.
n = 3.
In this case it is enough to verify only for m = 3. If p is an odd prime and p divides o(A). Define by
where o(a) = p. Thus
for all
If 4 divides o(A) and A has a subgroup isomorphic to then define
by
where a is generator of
Thus
for all
If A has a subgroup isomorphic to then define
by
Thus for all
A V4-vertex magic labeling of
is given in . □
Theorem 13.
The graph is group vertex magic if and only if (i)
(or) (ii) n > 3 and
Proof.
Let where
Assume that
is group vertex magic. Suppose
and n > 3. Since
which implies
Thus, we have
Further, if m is odd, then
If m is even, then
and
Therefore, the graph
is not
vertex magic, where p is an odd prime.
The converse part is given in three cases,
Case 1.
n = 2.
Then the graph if m is even. If m is odd, then
both are regular and hence group vertex magic.
Case 2.
n = 3
If p divides where p is an odd prime, then define
by
where o(a) = p. Thus
for all i, j.
Suppose 2 divides then define
by
for all i, j, where o(a) = 2. Then
for all i, j.
Case 3.
n > 3 and
Define by
where Thus
for all i, j. A group vertex magic labeling of
is given in . □
Remark 1.
From Theorem 13, admits A-vertex magic labeling, for
, but from Theorem 11, 12 the graphs
and
fails to admit A-vertex magic labeling, when
Definition 3.
[Citation9] The lexicographic product or graph composition of graphs G and H is a graph such that the vertex set of
is the product
and any two vertices (g, h) and
are adjacent in
if and only if either g is adjacent with
in G or
and h is adjacent with
in H.
Theorem 14.
Let A be an Abelian group, underlying a commutative ring R. If G1 is r-regular graph and there exists an A-vertex magic labeling for graph G2, then the lexicographic product
is A-vertex magic.
Proof.
Let us assume the magic constant of l2 is a and Let
Define
by
Assume that
and
Then
and
Now,
Since (u, v) is arbitrary, for all
□
Theorem 15.
Let G be any simple graph on n vertices. The graph is A-vertex magic, where
if and only if m > 1.
Proof.
Let and
Assume that
is A-vertex magic and m = 1. Then
but G need not be A-vertex magic.
Conversely, assume that
Suppose m is odd. Define by
where
Thus
for all
Suppose m is even. Define by
Thus for all
□
Remark 2.
In the above theorems wherever it is required to label the vertices of G using an infinite Abelian group, we follow the technique mentioned in case 3 of Theorem 3.
4. Conclusion and scope
In this paper, we have studied the A-vertex magicness for various graph operations namely, join, tensor and lexicographic product. In this direction one can investigate A-vertex magicness for other graph products.
Acknowledgements
The first author would like to thank K. Ayyanar for the support and fruitful discussions.
Additional information
Funding
References
- Bondy, J. A., Murty, U. S. R. (1976). Graph Theory with Applications. New York: American Elsevier Publishing Co., Inc.
- Herstein, I. N. (2006). Topics in Algebra, 2nd ed. New York: John Wiley and Sons.
- Kamatchi, N., Paramasivam, K., Prajeesh, A. V., Muhammed Sabeel, K, Arumugam, S. (2020). On group vertex magic graphs. AKCE Int. J. Graphs Comb. 17(1): 461–465.
- Kollaran, M. S., Prajeesh, A. V, Paramasivam, K. (2021). A characterization for V4-vertex magicness of trees with diameter 5. Commun. Comput. Inf. Sci.1345: 243–249.
- Lee, S. M., Saba, F., Salehi, E, Sun, H. (2002). On the V4-magic graphs. Congr. Numer. 156: 59–67.
- Low, R. M, Lee, S. M. (2006). On the products of group-magic graphs. Australas. J. Combin. 34: 41–48.
- Miller, M., Rodger, C, Simanjuntak, R. (2003). Distance magic labelings of graphs. Australas. J. Combin. 28: 305–315.
- Hammack, R., Imrich, W, Klavžar, S. (2016). Handbook of Product Graphs, 2nd ed. Boca Raton: CRC Press.
- West, D. B. (2001). Introduction of Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice Hall.