Antimagic labelings on graphs with ascending subgraph decomposition

Document Type : Research Paper

Authors

1 Doctoral Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

2 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

Abstract

Let $t$ and $q$ be positive integers that satisfy $\binom{t+1}{2} \leq q< \binom{t+2}{2}$ and $G$ be a simple and finite graph of size $q$. $G$ is said to be an ascending subgraph decomposition (ASD) graph if $G$ can be decomposed into $t$ subgraphs $H_1, H_2,\ldots,H_t$ without isolated vertices such that $H_i$ is isomorphic to a proper subgraph of $H_{i+1}$, for $1 \leq i \leq t-1$.
 
In this paper, we introduce a new type of antimagic labeling based on the notion of ASD. Let $G$ be an ASD graph and $f:V(G)\cup E(G) \rightarrow \{1,2,\ldots,\lvert V(G)\rvert+\lvert E(G)\rvert\}$ a bijection. The weight of a subgraph $H_i$ $(1\leq i\leq t)$ is $w(H_i)=\sum_{v\in V(H_i)}f(v)+\sum_{e\in E(H_i)}f(e)$. If the weights of all $H_i$s $(1\leq i\leq t)$ form an arithmetic progression with the smallest weight $a$ and common difference $d$, then $f$ is called an $(a,d)$-ASD antimagic labeling and $G$ is an $(a,d)$-ASD antimagic graph.
 
We provide an upper bound for $d$ in an $(a,d)$-ASD antimagic graph. We define and utilize the $(t,\delta)$-ascending antibalanced multisets to label some product graphs, including disjoint union, vertex amalgamation, edge amalgamation, subgraph amalgamation, and extended chain of graphs.

Keywords

Main Subjects

References

[1] 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.
[2] G. A. Barragán-Ramı́rez, R. Simanjuntak, S. W. Saputro and S. Uttunggadewa, The local metric dimension of subgraph-amalgamation of graphs, (2015), arXiv:1512.07420v1. https://doi.org/10.48550/arXiv.
1512.07420
[3] C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002) 17–26.
[4] C. Barrientos and S. Minion, Snakes: from graceful to harmonious, Bull. Inst. Combin. Appl., 79 (2017) 95–107.
[5] P. Erdös, A. Goodman and L. Posa, The representation of a graph by set intersection, Canadian J. Math., 18 (1966) 106–112.
[6] N. Inayah, A. Lladó and J. Moragas, Magic and antimagic H-decomposition, Discrete Math., 312 no. 7 (2012) 1367–1371.
[7] N. Inayah, A. N. M. Salman and R. Simanjuntak, On (a, d)-H-antimagic coverings of graphs, J. Combin. Math. Combin. Comput., 71 (2009) 273–281.
[8] N. Inayah, R. Simanjuntak, A. N. M. Salman, and K. I. A. Syuhada, Super (a, d)-H-antimagic total labelings for shackles of a connected graph H, Australas. J. Combin., 57 (2013) 127–138.
[9] Z. Liang and H. L. Fu, On ascending subgraph decomposition of graphs, J. Discrete Math. Sci. Cryptogr., 20 no. 5 (2017) 1135–1149.
[10] J. Petersen, Die theorie der regulären graphs, Acta Math., 15 no. 1 (1891) 193–220.
Transactions on Combinatorics
Volume 15, Issue 4 - Serial Number 4
December 2026
Pages 317-333

Files

History

  • Receive Date: 31 October 2024
  • Revise Date: 30 June 2025
  • Accept Date: 01 September 2025
  • Published Online: 01 December 2026

Share

How to cite

Statistics