![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be a graph of order n and let
be a bijection. For every vertex
, we define the weight of the vertex v as
where N(v) is the open neighborhood of the vertex v. The bijection f is said to be a local distance antimagic labeling of G if
for every pair of adjacent vertices
. The local distance antimagic labeling f defines a proper vertex coloring of the graph G, where the vertex v is assigned the color w(v). We define the local distance antimagic chromatic number
to be the minimum number of colors taken over all colorings induced by local distance antimagic labelings of G. In this paper we obtain the local distance antimagic labelings for several families of graphs including the path Pn, the cycle Cn, the wheel graph Wn, friendship graph Fn, the corona product of graphs
, complete multipartite graph and some special types of the caterpillars. We also find upper bounds for the local distance antimagic chromatic number for these families of graphs.
2010 MATHEMATICS SUBJECT CLASSIFICATION:
1 Introduction
By a graph , we mean a finite, undirected and connected graph with neither loops nor multiple edges. The order
and the size
are denoted by n and m, respectively. For graph theoretic terminology and notation we refer to Chartrand and Lesniak [Citation3].
The notion of antimagic labeling was introduced by Hartsfield and Ringel [Citation8] in 1990. A graph G is antimagic if the edges of G can be labeled by the numbers such that the sums of the labels of the edges incident to each vertex (called weight of a vertex) are distinct. Also they conjectured that every connected graph different from K2 is antimagic. This conjecture is still open.
Arumugam and Kamatchi [Citation2] considered a vertex version of antimagic labeling of a graph. Let be a graph of order n and let f be a bijection from V onto
. Given such a bijection f, the weight of a vertex is defined as:
, where N(v) is the open neighborhood of the vertex v, which is defined as the set of all vertices of the graph G which are adjacent to v. The bijection f is called distance antimagic labeling if all vertices have distinct vertex-weights. A graph is called distance antimagic if it admits a distance antimagic labeling (see [Citation9]). A distance antimagic labeling is said to be an
distance antimagic labeling if the set of vertex weights is
.
In [Citation1] Arumugam et al. introduced a local version of antimatic labeling as follows: let be a connected graph with
and
. A bijection
is called a local antimagic labeling if for any two adjacent vertices u and v,
, where
, and E(u) is the set of edges incident to u. Thus any local antimagic labeling induces a proper vertex coloring of G where the vertex v is assigned the color w(v). The local antimagic chromatic number
is the minimum number of colors taken over all colorings induced by local antimagic labelings of G.
Motivated by this concept, in 2018 Handa et al. [Citation6] introduced the notion of a local distance antimagic labeling as follows: let be a graph of order n and let
be a bijection. For every vertex
, define the weight of v as
. The labeling f is said to be a local distance antimagic labeling of G if
for every pair of adjacent vertices
. A graph which admits such a labeling is called a local distance antimagic graph. A local distance antimagic labeling induces a proper vertex coloring of the graph, with the vertex v assigned the color w(v). The local distance antimagic chromatic number
is the minimum number of colors taken over all colorings induced by local distance antimagic labelings of G (see [Citation7]). An illustration of a local distance antimagic labeling of
, and C4 are shown in .
Remark 1.1.
Every distance antimagic graph is local distance antimagic, but the converse is not true. For example, the graph P3 is local distance antimagic however it is not distance antimagic. Furthermore for every local distance antimagic graph G of order n, , where
is the chromatic number of the graph G.
The wheel graph Wn is the graph , formed by joining an isolated vertex to every vertex of a cycle Cn. The friendship graph Fn is a graph which consists of n triangles C3 with a common vertex (see ). A vertex v in a graph G is called a support vertex if it is adjacent to a vertex of degree 1 in G. A vertex of degree 1 is called a pendent vertex or a leaf.
The corona product of two graphs G and H is the graph obtained by taking one copy of G and copies of H and joining the ith vertex of G to every vertex in the ith copy of H. The corona product of G and H is denoted by
.
We now present an important result on magic rectangles which will be useful in our subsequent investigation. A magic rectangle is an a × b array with entries
, each appearing once, such that the sum of entries in each row is equal to
and the sum of each column is equal to
. The following theorem gives the necessary and sufficient condition for existence of a magic rectangle
.
Theorem 1.2.
[Citation5] For , there is a magic rectangle
if and only if
and
.
1.1 Local distance antimagic chromatic number of some graphs
For two sets A and B the symmetric difference is defined to be the set
.
Proposition 1.3.
Let G be a local distance antimagic graph of order n. If u, v are vertices such that , then
.
Proof.
Let be a local distance antimagic labeling of G. We consider the following two cases:
Case 1: Suppose . Let
such that
. Then
. Therefore,
.
Case 2: Suppose . Let
such that
. Without loss of generality suppose that
, then either
or
. If
, then
. On the other hand if
, then
. In both cases
, hence
. □
We begin our investigation of a local distance antimagic coloring of graphs with a path Pn. It is easy to see that and
(see ). For
we have the following result.
Proposition 1.4.
For a path Pn with .
Proof.
Let be a path on n vertices with
. Let f be a local distance antimagic labeling of Pn. We first calculate the weights of the vertices v0, v1 and v2. We shall show that these vertices have distinct weights, hence proving the result. Suppose
and
. Now, since v0 and v1 are adjacent vertices, therefore
. In the same way since v1 and v2 are adjacent, therefore
. Now, since
, therefore by Proposition 1.3,
. Therefore the vertices
have distinct weights and hence
. Examples of local distance antimagic labeling of P5 and P11 are shown in and respectively. □
Proposition 1.5.
For and
,
.
Proof.
Let be a path on n vertices with
and
. Let f be a local distance antimagic labeling of Pn. Since
, the labeling f admits at least three distinct vertex weights. Suppose that f admits exactly three distinct weights. Let
where
. From the previous proof we have seen that the weights
are distinct. Now we consider the following two cases:
Case 1: . Consider the weight of the vertex v3. Since v3 and v2 are adjacent, therefore
. Moreover, since
, therefore by Proposition 1.3,
. Now since the labeling f admits exactly 3 colors, it follows that
. Using the same argument we can show that
,
and so on. Hence
. Now, since
, it follows that
. However,
and
. Therefore
which contradicts the fact that f is a bijection. Hence the labeling f must admit at least 4 colors.
Case 2: . Now for each
,
and since
it follows that
. Now
and
. Therefore,
. Similarly
and
. Therefore,
. This is a contradiction. Hence for
and
. □
Lemma 1.6.
The path Pn is local distance antimagic with .
Proof.
Let be the vertex set of Pn. We define a local distance antimagic labeling f of Pn, which admits at most 6 distinct colors. We consider the following four cases:
Case 1: .
In this case, we define the vertex labels as follows:
Now the weight of vertices are as follows: and for
we have;
Case 2: .
Define the vertex labels as follows:
Following are the resulting vertex weights: and
.
For and n – 1,
Case 3: .
Define the vertex labels as follows:
Following are the resulting vertex weights.
For
and
.
Case 4: .
Define the vertex labels as follows:
Resulting vertex weights are as follows: ,
.
For .
In each of these cases, there are either five or six distinct weights (colors) of the vertices with respect to the labeling f, hence . This completes the proof. □
An illustration of a local distance antimagic labeling of P10 is shown in . A local distance antimagic labeling of P13 is shown in .
Theorem 1.7.
For the path Pn, and
.
Proof.
The proof follows from Proposition 1.5 and Lemma 1.6. □
Theorem 1.8.
For the path Pn, and
.
Proof.
The proof follows from Proposition 1.4 and Lemma 1.6. □
We now study the local distance antimagic coloring for the cycle Cn. For n = 3, the graph , hence
. For n = 4,
(see ). For
we have the following result.
Proposition 1.9.
For the cycle Cn, .
Proof.
Let be a cycle on n vertices with
. Let f be a local distance antimagic labeling of Cn. We first calculate the weights of the vertices v0, v1 and v2. We shall show that these weights are distinct, hence proving the result. Let
and
. Now, since v0 and v1 are adjacent vertices, therefore
. Similarly since v1 and v2 are adjacent, therefore
and since
, therefore by Proposition 1.3,
. Hence the weights
are distinct. Therefore,
. □
Proposition 1.10.
For and
.
Proof.
Let be a cycle on n vertices with
and
. Let f be a local distance antimagic labeling of Cn. By Proposition 1.9 the labeling f admits at least three distinct vertex weights. Suppose that f admits exactly three distinct weights. Let
. From the previous proof, the weights
are distinct. Now consider the weight of the vertex v3. Since v3 and v2 are adjacent, therefore
and since
, therefore by Proposition 1.3,
. Now since the labeling f admits exactly three distinct weights, it follows that w3 = w0. Using the same argument we can show that
and so on. Therefore
. Next consider the weight of the vertex
. Since
and v0 are adjacent, therefore
and since
, therefore by Proposition 1.3,
. Hence
, therefore
. Hence
which is a contradiction. Therefore for
and
. □
Lemma 1.11.
The cycle is a local distance antimagic graph with
.
Proof.
Let be the vertex set of Cn. We define a local distance antimagic labeling
as follows:
Case 1: n is even.
Now the weight of vertices are as follows: , when
and
, when
.
For the vertex weights are
Case 2: n is odd.
Now the vertex weights are as follows: for
and
when
,
For the vertex weights are
In each of the above cases, there are only six distinct weights, whenever . Hence
. This completes the proof. □
The illustration of a local distance antimagic labeling of C20 is shown in .
Theorem 1.12.
For the cycle Cn, .
Proof.
The proof follows from Proposition 1.9 and Lemma 1.11. □
Theorem 1.13.
For the cycle Cn, .
Proof.
The proof follows from Proposition 1.10 and Lemma 1.11. □
Proposition 1.14.
Let G be a local distance antimagic graph with m support vertices, then .
Proof.
Let be m support vertices of G. Let
be pendent vertices such that for
the vertex ui adjacent to vi. Then for any local distance antimagic labeling f of G,
. Therefore the vertices ui receive distinct weights under f. Hence
. □
Lemma 1.15.
For a local distance antimagic graph G, , where
is the clique number of G.
Proof.
Let be a clique of order
. Then for every local distance antimagic labeling f of G, each vertex in
receives a distinct weight under f. Hence it follows that
. □
Remark 1.16.
The complete graph Kn is local distance antimagic with .
Lemma 1.17.
The wheel graph Wn, is local distance antimagic with
.
Proof.
Let be the vertex set of Wn such that the vertices
form a cycle of length n and u is the central vertex of the wheel. We label the cycle using the labeling described in Lemma 1.11, and the vertex u is assigned the highest label n + 1. The resulting labeling is a local distance antimagic labeling of Wn which admits at most 7 distinct colors. By Lemma 1.15,
. Hence,
. □
Theorem 1.18.
Let G be a local distance antimagic graph of order n with , then for
,
.
Proof.
Let be the vertices of graph G and let
be the m pendant vertices adjacent to ui, in the graph
. By Theorem 1.2, for
, there exists a magic rectangle
of order m × n. Let
be the n columns of the magic rectangle
. Define
, where
. The sum of entries in
is
. Let
, be a local distance antimagic labeling of G which admits r distinct vertex weights. Let
be the vertex weights under the labeling f. We define a local distance antimagic labeling
of
as follows: for each i, define
and the vertices
are labeled with the elements of the column vector
. The resulting vertex weights under the labeling
are as follows:
, and
. The labeling
is a local distance antimagic labeling which admits at most n + r distinct colors. Hence
. This completes the proof. □
Theorem 1.19.
Let Fn be a friendship graph and r be a positive integer, then the graph rFn is local distance antimagic with .
Proof.
Let be the vertex set of rFn such that for a fixed i the set of vertices
forms one copy of Fn with the vertices
arranged as shown in . For every vertex
if j is odd and
if j is even. Let f be a local distance antimagic labeling of rFn. Consider the 2n vertices
in ith copy of Fn. Now for
, therefore by Proposition 1.3,
. Therefore the vertices
admit distinct vertex weights, hence
. Next we prove that
. We define a local distance antimagic labeling f of rFn as follows:
and
. The resulting vertex weights are
and
The labeling f is a local distance antimagic labeling which produces distinct vertex weights. Hence
. □
The illustration of a local distance antimagic labeling of is shown in .
Theorem 1.20.
The complete multipartite graph is local distance antimagic with
.
Proof.
Let be the partite sets of
with
, and
. Furthermore, let
. Now since
, it follows that
. We define a local distance antimagic labeling f of
which admits exactly r distinct vertex weights. We first label the vertices of V1 with the lowest m1 labels, followed by next higher m2 labels assigned to the vertices of V2. We continue in this manner until the vertices of Vr are labeled with the set of labels
. The labeling f is a local distance antimagic labeling which admits r distinct vertex weights. Therefore
. This completes the proof. □
Theorem 1.21.
Let G be a caterpillar with the central path of order n and m pendant vertices on each central vertex, then for .
Proof.
Let Pn denote the central path, let
be the vertices on the central path and
are the m pendant vertices adjacent to ui. Then
, hence the proof follows from the Lemma 1.6 and Theorem 1.18. □
The illustration of a local distance antimagic labeling of a caterpillar with central path P8 is shown in .
2 Conclusion and scope
In this paper, we have introduced the concept of local distance antimagic chromatic number of a graph. We found local distance antimagic labelings for several families of graphs including the path Pn, the cycle Cn, the wheel graph Wn, friendship graph Fn, the corona product of graphs , the complete multipartite graph and some special types of the caterpillars. We also obtain upper bounds for the local distance antimagic chromatic number for these families of graphs. Obtaining the exact value of the local distance antimagic chromatic number for these classes of graphs is a problem for further investigation. The concept of local distance antimagic labeling is also independently introduced and studied by Divya et al. [Citation4].
References
- Arumugam, S., Premalatha, K., Bača, M., Semaničová-Feňovčíková, A. (2017). Local antimagic vertex coloring of a graph. Graphs Comb. 33: 275–285.
- Arumugam, S., Kamatchi, N. (2015). On (a, d)-distance antimagic graphs. Australas. J. Comb. 54: 279–288.
- Chartrand, G., Lesniak, L. (2012). Graphs & Digraphs, 4th ed. Boca Raton, FL: Chapman and Hall, CRC.
- Divya, T., Yamini, S. Local distance antimagic vertex coloring of graphs. (preprint), arXiv:2106.01833.
- Hagedorn, T. R. (1999). Magic rectangles revisited. Discrete Math. 207: 65–72.
- Handa, A. K., Singh, T., Godinho, A. (2018). Local distance antimagic vertex coloring of graphs. In: International Conference on Discrete Mathematics and Its Applications (ICDMANS 2018), Organized by Department of Mathematics, BITS Pilani K K Birla Goa Campus, during July 7—10, 2018 (Abstract).
- Handa, A. K. (2021). Studies in distance antimagic graphs. Ph.D. Thesis. BITS Pilani, Pilani India.
- Hartsfield, N., Ringel, G. (1990). Pearls in Graph Theory. San Diego: Academic Press.
- Kamatchi, N. (2013). Distance magic and antimagic labeling of graphs. Ph.D. Thesis. Kalaslingam University, Tamil Nadu, India.