Antimagic orientation of forests

oriented vertex-sums are pairwise distinct, where the oriented vertex-sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. A graph

G

admits an antimagic orientation if

G

has an orientation

D

such that

D

has an antimagic labeling. Hefetz, M{"{u}}tze and Schwartz conjectured every connected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that any forest obtained from a given forest with at most one isolated vertex by subdividing each edge at least once admits an antimagic orientation.

Review text

An antimagic labeling of a directed graph with \(m\) arcs is a bijection from the set of arcs to the set \(\{1, 2, \dots, m\}\) such that any two oriented vertex-sums are distinct, where an oriented vertex-sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. A graph \(G\) admits an antimagic orientation if \(G\) has an orientation \(D\) such that \(D\) has an antimagic labeling. \textit{D. Hefetz} et al. [J. Graph Theory 64, No. 3, 219--232 (2010; Zbl 1209.05213)] introduced a variation of antimagic labelings on directed graphs, named antimagic orientation. Also, they proposed the following conjecture: every connected graph admits an antimagic orientation. The authors give the details of the previous studies on antimagic orientation. As a result of [\textit{G. Kaplan} et al., Discrete Math. 309, No. 8, 2010--2014 (2009; Zbl 1229.05031)], with a minor error corrected by \textit{Y.-C. Liang} et al. [ibid. 331, 9--14 (2014; Zbl 1297.05205)] on antimagic labelings of trees, the authors know that every tree with at most one vertex of degree two admits an antimagic orientation, and any tree obtained from a tree with no vertex of degree two by subdividing every edge exactly once admits an antimagic orientation. These two results, together with the result of the \textit{S. Shan} [J. Graph Theory 98, No. 4, 676--690 (2021; Zbl 1522.05408)] that every bipartite graph with no vertex of degree two or zero admits an antimagic orientation, suggest that it was hard to find an antimagic orientation if a graph has many vertices of degree two. The authors solve this problem for forests in this paper and obtain the key theorem. ``Let \(F = (V, E)\) be a forest with at most one isolated vertex. If the set of vertices of degree distinct from two is independent, then \(F\) admits an antimagic orientation. With the help of the following two lemmas, the authors prove the key theorem. First, they use the lemma to partition an integer set such that all the sums of the elements from each subset are congruent to zero modulo an integer. In the second lemma, they discuss how to label paths in a forest, which is used in the proof of the main theorem. This paper is written rather nicely. Reading this article will be very beneficial to the researcher. Researchers looking to do more studies on graph classes with antimagic orientation type labeling will find the works listed in the reference to be helpful.

Recommendations

Cites work

Cited in

(1)

Antimagic labeling of subdivided caterpillars

This page was built for publication: Antimagic orientation of forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080125)