Article in volume
Authors:
Title:
Trees whose even-degree vertices induce a path are antimagic
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 959-966
Received: 2019-08-30 , Revised: 2020-03-21 , Accepted: 2020-03-25 , Available online: 2020-05-01 , https://doi.org/10.7151/dmgt.2322
Abstract:
An antimagic labeling of a connected graph $G$ is a bijection from the
set of edges $E(G)$ to $\{1,2,\dots,|E(G)|\}$ such that all vertex sums are
pairwise distinct, where the vertex sum at vertex $v$ is the sum of the
labels assigned to edges incident to $v$. A graph is called antimagic if
it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that
every simple connected graph other than $K_2$ is antimagic; however the
conjecture remains open, even for trees. In this note we prove that trees whose
vertices of even degree induce a path are antimagic, extending a result given
by Liang, Wong, and Zhu [ Anti-magic labeling of trees, Discrete Math.
331 (2014) 9–14].
Keywords:
antimagic labeling, tree
References:
- F.H. Chang, P. Chin, W.T. Li and Z. Pan, The strongly antimagic labelings of double spiders (2017).
arXiv: 1712.09477 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (CRC Press Boca Raton, 2011).
- K. Deng and Y. Li, Caterpillars with maximum degree $3$ are antimagic, Discrete Math. 342 (2019) 1799–1801.
https://doi.org/10.1016/j.disc.2019.02.021 - J.A. Gallian, Graph labeling, Electron. J. Combin. 2018 (#DS6).
https://doi.org/10.37236/27 - N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press INC., Boston, 1990 (revised version, 1994).
- G. Kaplan, A. Lev and Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete Math. 309 (2009) 2010–2014.
https://doi.org/10.1016/j.disc.2008.04.012 - Y.-Ch. Liang, T.-L. Wong and X. Zhu, Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14.
https://doi.org/10.1016/j.disc.2014.04.021 - A. Lozano, M. Mora and C. Seara, Antimagic labelings of caterpillars, Appl. Math. Comput. 347 (2019) 734–740.
https://doi.org/10.1016/j.amc.2018.11.043 - A. Lozano, M. Mora, C. Seara and J. Tey, Caterpillars are antimagic (2018).
arXiv: 1812.06715 - J.L. Shang, Spiders are antimagic, Ars Combin. 118 (2015) 367–372.
Close