Prime Labelings of Trees
Abstract
A prime labeling of a graph labels its vertices bijectively with the integers from one to the number of vertices, so that adjacent vertices receive coprime labels. I prove the Entringer-Tout conjecture that every tree admits a prime labeling, extending the result of Haxell, Pikhurko, and Taraz from sufficiently large trees to all orders. My proof combines structural decompositions of trees, arithmetic organization of the labels, and matching arguments. I reduce the labeling problem to a structured bipartite matching problem by separating a small part of the tree, distributing labels according to their divisibility properties, and applying Hall's theorem to complete the labeling. I handle the finite and intermediate ranges using exact computer-assisted certificates whose validity is justified mathematically, while the remaining range is covered by analytic estimates. Together, these ingredients yield a proof for trees of every order.
Related
- Rainbow maps and the number of graceful labelings of trees
- On Multi-label radio Labelings of Graphs
- On a conjecture concerning antipodal labelings for cycles
- Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs
- Increasing Paths on N-ary Trees
BibTeX
@misc{ho2026prime,
title = {{Prime Labelings of Trees}},
author = {Dang Dung Ho},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02271},
eprint = {2610.02271},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02271},
}
RIS
TY - UNPB
TI - Prime Labelings of Trees
AU - Dang Dung Ho
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.02271
UR - https://arxiv.org/abs/2610.02271
AB - A prime labeling of a graph labels its vertices bijectively with the integers from one to the number of vertices, so that adjacent vertices receive coprime labels. I prove the Entringer-Tout conjecture that every tree admits a prime labeling, extending the result of Haxell, Pikhurko, and Taraz from sufficiently large trees to all orders. My proof combines structural decompositions of trees, arithmetic organization of the labels, and matching arguments. I reduce the labeling problem to a structured bipartite matching problem by separating a small part of the tree, distributing labels according to their divisibility properties, and applying Hall's theorem to complete the labeling. I handle the finite and intermediate ranges using exact computer-assisted certificates whose validity is justified mathematically, while the remaining range is covered by analytic estimates. Together, these ingredients yield a proof for trees of every order.
ER -