On the relations among edge magic total, edge antimagic total, and ASD-antimagic graphs
Abstract
Let G be a simple and finite graph of order p and size q. The graph G is said to be edge magic total (EMT) if there is a bijection λ:V(G)∪E(G)→{1,2,…,p+q} such that all edge sums λ(x)+λ(xy)+λ(y), xy∈E(G), are the same. If all edge sums are pairwise distinct, then G is called edge antimagic total (EAT). Let t be a positive integer that satisfies C(t+1,2)≤q<C(t+2,2). The graph G is said to have an ascending subgraph decomposition (ASD) if G can be decomposed into t subgraphs H1,H2,…,Ht without isolated vertices such that Hi is isomorphic to a proper subgraph of Hi+1 for 1≤i≤t−1. A graph that admits an ascending subgraph decomposition is called an ASD graph. An ASD graph G is said to be ASD-antimagic if there exists a bijection f:V(G)∪E(G)→{1,2,…,p+q} such that all subgraph weights w(Hi)=∑v∈V(Hi)f(v)+∑e∈E(Hi)f(e), 1≤i≤t, are distinct. In this paper, we provide constructions of ASD-antimagic graphs arising from EMT or EAT graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.2.11
References
I.H. Agustin, R.M. Prihandini, and Dafik, P2 ⊳ H-super antimagic total labeling of comb product of graphs, AKCE Int. J. Graphs Comb. 16 (2019), 163–171.
Y. Alavi, A.J. Boals, G. Chartrand, P. Erdős, and O.R. Oellermann, The ascending subgraph decomposition problem, Congr. Numer. 58 (1987), 7–14.
M. Bača, E.T. Baskoro, R. Simanjuntak, and K.A. Sugeng, Super edge-antimagic labelings of the generalized Petersen graph P(n,(n−1)/2), Util. Math. 70 (2006), 119–127.
M. Bača, Y. Lin, and F. A. Muntaner-Batle, Super edge-antimagic labelings of the path-like trees, Util. Math. 73 (2007), 117–128.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, (1976).
Dafik, Slamin, D. Tanna, A. Semaničová-Feňovčíková, and M. Bača, Constructions of H-antimagic graphs using smaller edge-antimagic graphs, Ars Combin. 133 (2022), 233–245.
Darmaji, S. Wahyudi, Rinurwati, and S.W. Saputro, On the construction of super edge-magic total graphs, Electron. J. Graph Theory Appl. 10 (1) (2022), 301–309.
J.P. Devi, S. Sripriya, K. Yogunath, and J. Nagapriya, Graph labeling for topological data analysis in machine learning, Int. J. Environ. Sci. 11 (12s) (2025), 273–281.
P. Erdős, A. Goodman, and L. Posa, The Representation of a graph by set intersections, Canad. J. Math. 18 (1966), 106–112.
R. Ichishima and F.A. Muntaner-Batle, On the super edge-magicness of graphs with a specific degree sequence, Open J. Discret. Appl. Math 6(3) (2023), 22–25.
N. Inayah, A. Lladó, and J. Moragas, Magic and antimagic H-decomposition, Discrete Math. 312 (2012), 1367–1371.
R. Jegan, P. Vijayakumar, and K. Thirusangu, A Coding algorithm using super-edge magic total labeling of extended duplicate graphs, Proc. 2022 Second Int. Conf. Comput. Sci., Eng. Appl. (ICCSEA), GIET University, Gunupur, India (2022), 1–6.
R. Jegan, P. Vijayakumar, and K. Thirusangu, Encrypting a word using super-edge antimagic and super-edge magic total labeling of extended duplicate graphs, Indian J. Comput. Sci. Eng. (IJCSE) 13(5) (2023), 1559–1565.
A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970), 451–461.
Z. Liang and H.L. Fu, On ascending subgraph decomposition of graphs, J. Discrete Math. Sci. Cryptogr. 20(5) (2017), 1135–1149.
T.K. Maryati, F.F. Hadiputra, and A.N.M. Salman, Forbidden family of Ph-magic graphs, Electron. J. Graph Theory Appl. 12 (1) (2024), 43–54.
S. Pancahayani, R. Simanjuntak, and S. Uttunggadewa, Magic labeling on graphs with ascending subgraph decomposition, Electron. J. Graph Theory Appl. 12 (2) (2024), 189–203.
S. Pancahayani, R. Simanjuntak, and S. Uttunggadewa, Antimagic labelings on graphs with ascending subgraph decomposition, Trans. Comb. (2024), in press.
R. Simanjuntak and M. Miller, Survey of (a,d)-antimagic graph labelings, MIHMI 6 (2000), 179–184.
Z. Liang, On magic total labelings in combinatorial designs, J. Inf. Optim. Sci 45(1) (2024), 47–56.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.