Tree labeling inequality fails for caterpillars with many internal vertices
Counterexamples to the local antimagic leaf conjecture
Discrete Mathematics
Summary
This paper studies a math puzzle about labeling the connections (edges) in tree-shaped graphs so that the sums at each point (vertex) create a special color pattern. Previously, it was guessed that the number of colors needed relates closely to the number of endpoints (leaves) in the tree plus a small fixed number. The authors found examples where this number is much bigger, showing the guess is false even for simple tree structures called caterpillars. They also prove that no fixed number can replace the small fixed number in every case.
What this means in practice
- •For network designers: Understand limitations in edge labeling schemes for network nodes that ensure distinct data summaries.
- •For graph algorithm developers: Avoid relying on fixed upper bounds for local antimagic chromatic numbers when designing algorithms with tree labelings.
A theory result. No direct application yet.
Authors
André Ebling Brondani, Francisca Andrea Macedo França
Abstract
It has been conjectured that $χ_{\mathrm{la}}(T)\leq\ell(T)+2$ for every tree $T$ of order at least three, where $χ_{\mathrm{la}}(T)$ is the local antimagic chromatic number and $\ell(T)$ denotes the number of leaves. We disprove this bound and show that no absolute constant can replace $2$ in an inequality of this form. Our approach uses degree-based intervals containing all possible induced vertex weights under bijective edge labelings, together with a separation criterion that forces selected internal vertex weights to be distinct. We first construct caterpillars $T_3$ and $T_4$ satisfying $χ_{\mathrm{la}}(T_3)=\ell(T_3)+3$ and $χ_{\mathrm{la}}(T_4)=\ell(T_4)+4$, respectively. We then construct, for every positive integer $r$, infinitely many pairwise nonisomorphic caterpillars with exactly $r$ internal vertices for which every bijective edge labeling is antimagic. Each such caterpillar $T$ satisfies $χ_{\mathrm{la}}(T)=|V(T)|=\ell(T)+r$. Consequently, $χ_{\mathrm{la}}(T)-\ell(T)$ is unbounded even within the class of caterpillars, and no absolute constant $C$ can satisfy $χ_{\mathrm{la}}(T)\leq\ell(T)+C$ for every tree $T$.