D-antimagic labelings arising from completely separating systems
Abstract
Let D be a non-empty subset of the distance set {0,1,…, diam(G)}. A graph G is D-antimagic if there exists a bijection f:V(G)→{1,2,…,|V(G)|} such that for every pair of distinct vertices x and y, wD(x) ≠ wD(y), where wD(x) = Σz∈ND(x)f(z) is the D-weight of x and ND(x) = {z|d(x,z)∈D} is the D-neighbourhood of x. It was conjectured that a graph G is D-antimagic if and only if each vertex in G has a distinct D-neighborhood. A completely separating system (CSS) in the finite set {1,2,…,n} is a collection 𝒞 of subsets of {1,2,…,n} in which for each pair a≠b∈{1,2,…,n}, there exist A,B∈𝒞 such that a∈A−B and b∈B−A.
In this paper, we provide evidence to support the conjecture mentioned earlier by using Roberts' completely separating systems to define D-antimagic labelings for certain graphs. In particular, we show that if G and H are D-antimagic graphs with labelings constructed from Roberts' CSS, then the vertex-deleted subgraph, G−{v} and the vertex amalgamation of G and H are also D-antimagic. Additionally, we partially answer an open problem of Simanjuntak et al. (2021) by constructing {1}-antimagic labelings for some disjoint unions of paths.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.2.2
References
N. Alon, G. Kaplan, A. Lev, Y. Roditty, and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004), 297–309.
Y. Anjali and S. Minirani, A computer-aided algorithm to determine distance antimagic labeling of some graphs, Eng. Lett. 32 (2024), 269–275.
K. Bérczi, A. Bernáth, and M. Vizer, Regular graphs are antimagic, Electron. J. Comb. 22 (2015), P3.34.
F. Chang, Y. Liang, Z. Pan, and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2005), 338–249.
A. Chavez, P. Le, D. Lin, D. Liu, and M. Shurman, Antimagic labeling for unions of graphs with many three-paths, Discrete Math. 346 (2023), 113356.
Y. Cheng, A new class of antimagic cartesian product graphs, Discrete Math. 308 (2008), 6441–6448.
D. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009), 173–182.
K. Deng and Y. Li, Caterpillars with maximum degree 3 are antimagic, Discrete Math. 342 (2019), 1799–1801.
T. Dickson, On a problem concerning separating systems of a finite set, J. Comb. Theory Ser. A 7 (1969), 191–196.
T. Eccles, Graphs of large linear size are antimagic, J. Graph Theory 81 (2014), 162–176.
D. Fitriani and M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb. 13 (2016), 90–99.
N. Hartsfield and G. Ringel, Pearls in Graph Theory, A Comprehensive Introduction. Academic Press Inc., Boston (1990).
D. Hefetz, A. Saluz, and T. Tran, An application of the combinatorial nullstellensatz to a graph labeling problem, J. Graph Theory 65 (2009), 70–82.
N. Kamatchi and S. Arumugam, Distance antimagic graphs, J. Combin. Math. Combin. Comput. 64 (2013), 61–67.
N. Kamatchi, G. Vijayakumar, A. Ramalakshmi, S. Nilavarasi, and S. Arumugam, Distance antimagic labelings of graphs, Theor. Comput. Sci. and Discret. Math. 10398 (2017), 113–118.
A. Lladó and M. Miller, Approximate results for rainbow labeling, Period. Math. Hung. 74 (2016), 1–11.
A. Lozano, M. Mora, C. Seara, and J. Tey, Caterpillars are antimagic, Mediterr. J. Math. 39 (2021).
A.A.G. Ngurah, N. Inayah, and M.I.S. Musti, On d-distance (anti)magic labelings of shadow graph of some graphs, Electron. J. Graph Theory Appl. 12 (1) (2024), 25–34.
O. Phanalasy, M. Miller, L. Rylands, and P. Lieby, On a relationship between completely separating system and antimagic labeling of regular graphs, IWOCA 2010 LNCS 6460 (2011), 238–241.
A. Renyi, On random generating elements of a finite boolean algebra, Acta. Sci. Math. 22 (1961), 75–81.
I. Roberts, Extremal Problems and Designs on Finite Sets, Ph.D.
thesis, Curtin University of Technology (1999).
N. Shrimali and Y. Parmar, Distance Magic and Distance Antimagic Labeling of Some Product Graphs, Recent Advancements in Graph Theory, CRC Press, (2020), 181–191.
R. Simanjuntak and A. Tritama, Distance antimagic product graphs, Symmetry 14 (2022), 1411.
R. Simanjuntak, T. Nadeak, F. Yasin, K. Wijaya, Nurdin, and K. Sugeng, Another antimagic conjecture, Symmetry 13 (2021), 2071.
S. Syafrizal, R. Simanjuntak, T. Nadeak, K. Sugeng, and T. Tulus, Distance antimagic labeling of circulant graphs, AIMS Mathematics 9 (2024), 21177–21188.
R. Wulandari and R. Simanjuntak, Distance antimagic of product graphs, Electron. J. Graph Theory Appl. 11 (1) (2023), 111–123.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.