List-distance consistent vertices in trees are confined to a path
Abstract
A labeling of a connected graph G on n vertices is a bijection c:V(G)→{1,…,n}; writing c(u,v)=|c(u)−c(v)|, a vertex u is list-distance consistent if d(u,v)<d(u,w) implies c(u,v)≤ c(u,w) for all v,w. The maximum number of such vertices over all labelings is the list-distance consistency ldc(G), introduced by Casselgren and Henricsson. We prove that in a tree, the consistent vertices of any labeling lie on a single path, along which the labels form a block of consecutive integers in increasing order (with respect to a suitable orientation of the path), no vertex off the path receiving a label from that block. We deduce that ldc equals $3$ for every complete k-ary tree except the binary tree of height two, and we determine ldc for all spiders.
Related
- A Moser-spindle-free 5-chromatic unit distance graph on 2131 vertices in the plane
- Two-distance and list-two-distance coloring of cacti: the subcubic case and the C5 obstruction
- Multicolor Ramsey and list Ramsey numbers for star-like trees
- Uniform integrability of the distance to the nearest leaf in random trees
- Some results on the distance spectral radius and edge-disjoint spanning trees of graphs
BibTeX
@misc{chang2026listdistance,
title = {{List-distance consistent vertices in trees are confined to a path}},
author = {Fei-Huang Chang and Ma-Lian Chia and David Kuo and Guan-Ting Lai},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03803},
eprint = {2609.03803},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03803},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - List-distance consistent vertices in trees are confined to a path
AU - Fei-Huang Chang
AU - Ma-Lian Chia
AU - David Kuo
AU - Guan-Ting Lai
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03803
UR - https://arxiv.org/abs/2609.03803
AB - A labeling of a connected graph G on n vertices is a bijection c:V(G)→{1,…,n}; writing c(u,v)=|c(u)−c(v)|, a vertex u is list-distance consistent if d(u,v)<d(u,w) implies c(u,v)≤ c(u,w) for all v,w. The maximum number of such vertices over all labelings is the list-distance consistency ldc(G), introduced by Casselgren and Henricsson. We prove that in a tree, the consistent vertices of any labeling lie on a single path, along which the labels form a block of consecutive integers in increasing order (with respect to a suitable orientation of the path), no vertex off the path receiving a label from that block. We deduce that ldc equals $3$ for every complete k-ary tree except the binary tree of height two, and we determine ldc for all spiders.
ER -