Abstract
Let $G(V,E)$ be a graph with $V(G)$ as the set of vertices and $E(G)$ as the set of edges. A labeling is a bijection $f:E(G)\to\{1,2,\cdots, |E(G)|\}$. For each vertex \(v\), let \(\phi(v)\) be the sum of the labels on the edges incident to \(v\). If all values \(\phi(v)\) are distinct, the labeling is antimagic, and the graph is antimagic if such a labeling exists. This paper explores the concept of antimagic labeling in graph theory, with a particular focus on the union of various tree structures, including stars, single brooms, and double brooms. We apply extended Skolem sequences to prove that for a wide range of parameters, unions of multiple 3-paths with appropriately many 4-cycles yield antimagic graphs. Additionally, we analyze combinations of 4-cycles paired with different tree structures.
Full text article
References
A. Amanto, W. Wamiliana, M. Usman, and R. Permatasari, “Counting the number of disconnected vertex labelled graphs with order maximal four,” Science International Lahore, vol. 29, no. 6, pp. 1181–1186, 2017. http://repository.lppm.unila.ac.id/4822/.
A. Rosa et al., “On certain valuations of the vertices of a graph,” in Theory of Graphs (Internat. Symposium, Rome, pp. 349–355, 1966.
S. W. Golomb, “How to number a graph,” in Graph theory and computing, pp. 23–37, Elsevier, 1972. https://doi.org/10.1016/B978-1-4832-3187-7.50008-8.
N. Hartsfield and G. Ringel, “Pearls in graph theory academic press,” United Kingdom, 1994.
R. M. Prihandini and R. Adawiyah, “On super (3n + 5, 2)-edge antimagic total labeling and its application to construct hill cipher algorithm,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 17, no. 1, pp. 29–36, 2023. https://doi.org/10.30598/barekengvol17iss1pp0029-0036.
D. K. Gurjar and A. Krishnaa, “Various antimagic labeled graphs from graph theory for cryptography applications,” Int. J. Sci. Res. Math. Stat. Sci, vol. 9, no. 3, pp. 11–18, 2022. https://doi.org/10.26438/ijsrmss/v9i3.1118.
J. T. Gondalia, Anti-Magic Type Labeling: Fascinating Way of Graph Labeling. Rigi Publication, 2022.
G. Kaplan, A. Lev, and Y. Roditty, “On zero-sum partitions and anti-magic trees,” Discrete Mathematics, vol. 309, no. 8, pp. 2010–2014, 2009. https://doi.org/10.1016/j.disc.2008.04.012.
Y.-C. Liang, T.-L. Wong, and X. Zhu, “Anti-magic labeling of trees,” Discrete mathematics, vol. 331, pp. 9–14, 2014. https://doi.org/10.1016/j.disc.2014.04.021.
A. Lozano, M. Mora, and C. Seara, “Antimagic labelings of caterpillars,” Applied Mathematics and Computation, vol. 347, pp. 734–740, 2019. https://doi.org/10.1016/j.amc.2018.11.043.
T.-L. Wong and X. Zhu, “Antimagic labelling of vertex weighted graphs,” Journal of Graph Theory, vol. 70, no. 3, pp. 348–350, 2012. https://doi.org/10.1002/jgt.20624.
K. Deng and Y. Li, “Caterpillars with maximum degree 3 are antimagic,” Discrete Mathematics, vol. 342, no. 6, pp. 1799–1801, 2019. https://doi.org/10.1016/j.disc.2019.02.021.
J.-L. Shang, C. Lin, and S.-C. Liaw, “On the antimagic labeling of star forests,” Util. Math, vol. 97, pp. 373–385, 2015.
F.-H. Chang, P. Chin, W.-T. Li, and Z. Pan, “The strongly antimagic labelings of double spiders,” 2017. https://arxiv.org/abs/1712.09477.
J. Sierra, D. D.-F. Liu, and J. Toy, “Antimagic labelings of forests,” 2023. https://arxiv.org/abs/2307.16836.
M. D. Barrus, “Antimagic labeling and canonical decomposition of graphs,” Information Processing Letters, vol. 110, no. 7, pp. 261–263, 2010. https://doi.org/10.1016/j.ipl.2010.01.006.
H. V. Chen, “A total labellings of m triangles,” Tamkang Journal of Mathematics, vol. 41, no. 4, pp. 393–402, 2010. https://doi.org/10.5556/j.tkjm.41.2010.788.
M. Baˇca, A. Semaniˇcov´a-Feˇnovˇc´ıkov´a, and T.-M. Wang, “Local antimagic chromatic number for copies of graphs,” Mathematics, vol. 9, no. 11, p. 1230, 2021. https://doi.org/10.3390/math9111230.
R. Simanjuntak, T. Nadeak, F. Yasin, K. Wijaya, N. Hinding, and K. A. Sugeng, “Another antimagic conjecture,” Symmetry, vol. 13, no. 11, p. 2071, 2021. https://doi.org/10.3390/sym13112071.
Y. B. Tai, G. L. Chia, and P.-H. Ong, “Multi-bridge graphs are anti-magic.,” Electronic Journal of Graph Theory & Applications, vol. 10, no. 1, pp. 311–318, 2022. https://dx.doi.org/10.5614/ejgta.2022.10.1.22.
J. A. Gallian, “A dynamic survey of graph labeling,” Electronic Journal of combinatorics, vol. 6, no. 25, pp. 4–623, 2022. https://doi.org/10.37236/11668.
T. Wang, M. Liu, and D. Li, “Some classes of disconnected antimagic graphs and their joins,” Wuhan University Journal of Natural Sciences, vol. 17, no. 3, pp. 195–199, 2012. https://doi.org/10.1007/s11859-012-0827-2.
J.-L. Shang, “Antimagic labeling of linear forests,” Util. Math, vol. 106, pp. 23–37, 2018.
P. Ghosh and A. Pal, “Some results of labeling on broom graph,” Journal: Journal of Advances in Mathematics, vol. 9, no. 9, pp. 3055–3061, 2015. https://doi.org/10.24297/jam.v9i9.2239.
R. S. Vinatih and B. D. Indriati, “Edge irregular reflexive labeling on double broom graph and comb of cycle and star graph,” TWMS Journal of Applied and Engineering Mathematics, vol. 15, no. 3, pp. 748–761, 2025. https://jaem.isikun.edu.tr/web/images/articles/vol.15.no.3/20.pdf.
C. J. Colbourn, CRC handbook of combinatorial designs. CRC press, 2010.
J. Abrham and A. Kotzig, “Skolem sequences and additive permutations,” Discrete Mathematics, vol. 37, no. 2-3, pp. 143–146, 1981. https://doi.org/10.1016/0012-365X(81)90214-4.
Authors
Copyright (c) 2026 Journal of the Indonesian Mathematical Society
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Article Details
