×

Approximate results for rainbow labelings. (English) Zbl 1399.05191

Summary: A simple graph \(G = (V, E)\) is said to be antimagic if there exists a bijection \(f : E \mapsto [1, | E|]\) such that the sum of the values of \(f\) on edges incident to a vertex takes different values on distinct vertices. The graph \(G\) is distance antimagic if there exists a bijection \(f : V \mapsto [1, | V|]\), such that \(\forall x, y \in V\), \[ \sum_{x_i\in N(x)}\neq \sum_{x_j\in N(y)} f(x_j). \] Using the polynomial method of N. Alon [Comb. Probab. Comput. 8, No. 1–2, 7–29 (1999; Zbl 0920.05026)] we prove that there are antimagic injections of any graph \(G\) with \(n\) vertices and \(m\) edges in the interval \([1, 2n+m-4]\) and, for trees with \(k\) inner vertices, in the interval \([1, m+k]\). In particular, a tree all of whose inner vertices are adjacent to a leaf is antimagic. This gives a partial positive answer to a conjecture by N. Hartsfield and G. Ringel [Pearls in graph theory. A comprehensive introduction. Rev. and augmented ed. Orlando, FL: Academic Press (1994; Zbl 0823.05001)]. We also show that there are distance antimagic injections of a graph \(G\) with order \(n\) and maximum degree \(\Delta\) in the interval \([1, n+t (n-t)]\), where \(t = \min \{\Delta, [n/2]\}\), and, for trees with \(k\) leaves, in the interval \([1, 3n - 4k]\). In particular, all trees with \(n = 2k\) vertices and no pairs of leaves sharing their neighbour are distance antimagic, a partial solution to a conjecture of Arumugam.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] N. Alon, Combinatorial Nullstellensatz. Comb. Probab. Comput. 8, 7–29 (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411
[2] N. Alon, Additive Latin transversals. Isr. J. Math. 117, 125–130 (2000) · Zbl 1047.11019 · doi:10.1007/BF02773567
[3] N. Alon, G. Kaplan, A. Lev, Y. Roditty, R. Yuster, Dense graphs are antimagic. J. Graph Theory 47(4), 297–309 (2004) · Zbl 1055.05132 · doi:10.1002/jgt.20027
[4] S. Arumugam, personal communication (2012)
[5] M. Bača, M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions (BrownWalker Press, Boca Raton, 2008)
[6] B. Bollobás, O. Pikhurko, Integer sets with prescribed pairwise differences being distinct. Eur. J. Comb. 26(5), 607–616 (2005) · Zbl 1062.05126 · doi:10.1016/j.ejc.2004.04.008
[7] P.D. Chawathe, V. Krishna, Antimagic Labeling of Complete m-Ary Trees, Number Theory and Discrete Mathematics, Trends in Mathematics (Birkhäuser, Basel, 2002) · Zbl 1028.05100
[8] Y. Cheng, Lattice grids and prisms are antimagic. Theor. Comput. Sci. 374(1–3), 66–73 (2007) · Zbl 1162.05040 · doi:10.1016/j.tcs.2006.12.003
[9] Y. Cheng, A new class of antimagic Cartesian product graphs. Discrete Math. 308(24), 6441–6448 (2008) · Zbl 1211.05140 · doi:10.1016/j.disc.2007.12.032
[10] D.W. Cranston, Regular bipartite graphs are antimagic. J. Graph Theory 60(3), 173–182 (2009) · Zbl 1210.05141 · doi:10.1002/jgt.20347
[11] J.A. Gallian, A dynamic survey of graph labeling. Electron. J. Comb. Dyn. Surv. # DS6 Eighteen Edition (2015) · Zbl 0953.05067
[12] N. Hartsfield, G. Ringel, Pearls in Graph Theory (Academic, Boston, 1994) · Zbl 0823.05001
[13] D. Hefetz, Anti-magic graphs via the combinatorial NullStellenSatz. J. Graph Theory 50(4), 263–272 (2005) · Zbl 1076.05068 · doi:10.1002/jgt.20112
[14] G. Kaplan, A. Lev, Y. Roditty, On zero-sum partitions and anti-magic trees. Discrete Math. 309, 2010–2014 (2009) · Zbl 1229.05031 · doi:10.1016/j.disc.2008.04.012
[15] R.N. Karasev, F.V. Petrov, Partitions of nonzero elements of a finite field into pairs. Isr. J. Math. 192, 143–156 (2012) · Zbl 1287.11015 · doi:10.1007/s11856-012-0020-5
[16] A. Lladó, S.C. López, J. Moragas, Every tree is a large subtree o · Zbl 1208.05013 · doi:10.1016/j.disc.2009.09.021
[17] M. Miller, C. Rodger, R. Simantujak, Distance magic labelings of graphs. Australas. J. Comb. 28, 305–315 (2003) · Zbl 1031.05117
[18] J. Ryan, O. Phanalasy, M. Miller, L.J. Rylands, in Combinatorial Algorithms, ed. by C.S. Iliopoulos, W.F. smyth. On Antimagic Labeling for Generalized Web and Flower Graphs. Lecture Notes in Computer Science, vol. 6460 (Springer, London, 2010), pp. 303–313 · Zbl 1326.05139
[19] T.-M. Wang, in Toroidal Grids are Antimagic. Proceedings of the 11th Annual International Computing and Combinatorics Conference, COCOON’2005. LNCS, vol. 3595 (Springer, Heidelberg, 2005), pp. 671–679
[20] T.-M. Wang, C.C. Hsiao, On anti-magic labeling for graph products. Discrete Math. 308(16), 3624–3633 (2008) · Zbl 1155.05055 · doi:10.1016/j.disc.2007.07.027
[21] Y. Zhang, X. Sun, The antimagicness of the Cartesian product of graphs. Theor. Comput. Sci. 410(8–10), 727–735 (2009) · Zbl 1162.05042 · doi:10.1016/j.tcs.2008.10.023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.