Distance antimagic labeling of circulant graphs

Syafrizal Sy; Rinovia Simanjuntak; Tamaro Nadeak; Kiki Ariyanti Sugeng; Tulus Tulus; Syafrizal Sy; Rinovia Simanjuntak; Tamaro Nadeak; Kiki Ariyanti Sugeng; Tulus Tulus

doi:10.3934/math.20241028

AIMS Mathematics

2024, Volume 9, Issue 8: 21177-21188. doi: 10.3934/math.20241028

Previous Article Next Article

Research article Special Issues

Distance antimagic labeling of circulant graphs

1.
Department of Mathematics and Data Science, Universitas Andalas, Indonesia
2.
Combinatorial Mathematics Research Group, Institut Teknologi Bandung, Indonesia
3.
Department of Data Science, Institut Teknologi Sumatera, Indonesia
4.
Department of Mathematics Universitas Indonesia, Indonesia
5.
Department of Mathematics, Universitas Sumatera Utara, Indonesia
6.
Center for Research Collaboration on Graph Theory and Combinatorics, Indonesia

Received: 11 December 2023 Revised: 25 March 2024 Accepted: 22 April 2024 Published: 01 July 2024
MSC : 05C78

A distance antimagic labeling of graph $ G = (V, E) $ of order $ n $ is a bijection $ f:V(G)\rightarrow \{1, 2, \ldots, n\} $ with the property that any two distinct vertices $ x $ and $ y $ satisfy $ \omega(x)\ne\omega(y) $, where $ \omega(x) $ denotes the open neighborhood sum $ \sum_{a\in N(x)}f(a) $ of a vertex $ x $. In 2013, Kamatchi and Arumugam conjectured that a graph admits a distance antimagic labeling if and only if it contains no two vertices with the same open neighborhood. A circulant graph $ C(n; S) $ is a Cayley graph with order $ n $ and generating set $ S $, whose adjacency matrix is circulant. This paper provides partial evidence for the conjecture above by presenting distance antimagic labeling for some circulant graphs. In particular, we completely characterized distance antimagic circulant graphs with one generator and distance antimagic circulant graphs $ C(n; \{1, k\}) $ with odd $ n $.
- graph labeling,
- antimagic labeling,
- distance antimagic labeling,
- circulant graph
Citation: Syafrizal Sy, Rinovia Simanjuntak, Tamaro Nadeak, Kiki Ariyanti Sugeng, Tulus Tulus. Distance antimagic labeling of circulant graphs[J]. AIMS Mathematics, 2024, 9(8): 21177-21188. doi: 10.3934/math.20241028

Related Papers:

Abstract

A distance antimagic labeling of graph $ G = (V, E) $ of order $ n $ is a bijection $ f:V(G)\rightarrow \{1, 2, \ldots, n\} $ with the property that any two distinct vertices $ x $ and $ y $ satisfy $ \omega(x)\ne\omega(y) $, where $ \omega(x) $ denotes the open neighborhood sum $ \sum_{a\in N(x)}f(a) $ of a vertex $ x $. In 2013, Kamatchi and Arumugam conjectured that a graph admits a distance antimagic labeling if and only if it contains no two vertices with the same open neighborhood. A circulant graph $ C(n; S) $ is a Cayley graph with order $ n $ and generating set $ S $, whose adjacency matrix is circulant. This paper provides partial evidence for the conjecture above by presenting distance antimagic labeling for some circulant graphs. In particular, we completely characterized distance antimagic circulant graphs with one generator and distance antimagic circulant graphs $ C(n; \{1, k\}) $ with odd $ n $.

References

[1]	S. Arumugam, D. Froncek, N. Kamatchi, Distance magic graphs–a survey, J. Indones. Math. Soc., 2011, 11–26. https://doi.org/10.22342/jims.0.0.15.11-26
[2]	S. Arumugam, N. Kamatchi, G. R. Vijayakumar, On the uniqueness of D-vertex magic constant, Discuss. Math. Graph Theory, 34 (2014), 279–286. https://doi.org/10.7151/dmgt.1728 doi: 10.7151/dmgt.1728
[3]	F. Boesch, R. Tindell, Circulants and their connectivity, J. Graph Theory, 8 (1984), 487–499. https://doi.org/10.1002/jgt.3190080406 doi: 10.1002/jgt.3190080406
[4]	S. Cichacz, D. Froncek, Distance magic circulant graphs, Discrete Math., 339 (2016), 84–94. https://doi.org/10.1016/j.disc.2015.07.002 doi: 10.1016/j.disc.2015.07.002
[5]	J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 2023. https://doi.org/10.37236/27
[6]	A. Godinho, T. Singh, Some distance magic graphs, AKCE Int. J. Graphs Combin., 15 (2018), 1–6. https://doi.org/10.1016/j.akcej.2018.02.004
[7]	N. Kamatchi, S. Arumugam, Distance antimagic graphs, J. Combinat. Math. Combinat. Comput., 64 (2013), 61–67.
[8]	N. Kamatchi, G. R. Vijayakumar, A. Ramalakshmi, S. Nilavarasi, S. Arumugam, Distance antimagic labelings of graphs, In: Theoretical computer science and discrete mathematics, 10398 (2017), 113–118. https://doi.org/10.1007/978-3-319-64419-6_15
[9]	C. H. Li, On isomorphisms of finite Cayley graphs–a survey, Discrete Math., 256 (2002), 301–334. https://doi.org/10.1016/S0012-365X(01)00438-1 doi: 10.1016/S0012-365X(01)00438-1
[10]	A. Llado, M. Miller, Approximate results for rainbow labeling, Period. Math. Hungar., 74 (2017), 11–21. https://doi.org/10.1007/s10998-016-0151-2 doi: 10.1007/s10998-016-0151-2
[11]	M. Muzychuk, On Adam's conjecture for circulant graphs, Discrete Math., 176 (1997), 285–298. https://doi.org/10.1016/S0012-365X(97)81804-3 doi: 10.1016/S0012-365X(97)81804-3
[12]	S. Miklavic, P. Sparl, Classification of tetravalent distance magic circulant graphs, Discrete Math., 344 (2021), 112557. https://doi.org/10.1016/j.disc.2021.112557 doi: 10.1016/j.disc.2021.112557
[13]	S. Miklavic, P. Sparl, On distance magic circulants of valency 6, Discrete Appl. Math., 329 (2023), 35–48. https://doi.org/10.1016/j.dam.2022.12.024 doi: 10.1016/j.dam.2022.12.024
[14]	A. O'Neal, P. J. Slater, Uniqueness of vertex magic constants, SIAM J. Discrete Math., 27 (2013), 708–716. https://doi.org/10.1137/110834421 doi: 10.1137/110834421
[15]	S. K. Patel, J. Vasava, Some results on $(a, d)$-distance antimagic labeling, Proyecciones, 39 (2020), 361–381. https://doi.org/10.22199/issn.0717-6279-2020-02-0022 doi: 10.22199/issn.0717-6279-2020-02-0022
[16]	M. F. Semeniuta, $(a, d)$-distance antimagic labeling of some types of graphs, Cybernet. Syst. Anal., 52 (2016), 950–955. https://doi.org/10.1007/s10559-016-9897-z doi: 10.1007/s10559-016-9897-z
[17]	N. P. Shrimali, A. K. Rathod, $(a, d)$-distance antimagic labeling for some regular graphs, Malaya J. Mat., 9 (2021), 1118–1122.
[18]	R. Simanjuntak, T. Nadeak, F. Yasin, K. Wijaya, N. Hinding, K. A. Sugeng, Another antimagic conjecture, Symmetry, 13 (2021), 1–15. https://doi.org/10.3390/sym13112071 doi: 10.3390/sym13112071
[19]	R. Simanjuntak, A. Tritama, Distance antimagic product graphs, Symmetry, 14 (2022), 1–15. https://doi.org/10.3390/sym14071411 doi: 10.3390/sym14071411
[20]	V. Vilfred, Sigma-labelled graphs and circulant graphs, Ph.D. Thesis, India: University of Kerala, 1994.
[21]	R. Y. Wulandari, R. Simanjuntak, Distance antimagic labelings of product graphs, Electron. J. Graph Theory Appl., 11 (2023), 111–123. https://doi.org/10.5614/ejgta.2023.11.1.9 doi: 10.5614/ejgta.2023.11.1.9

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)