Extremal List Gaps and Inapproximability in Additive Graph Labeling
Abstract
We study a vertex-labeling analogue of the $1−2−3$ problem and its list version. For a labeling ℓ:V(G)→ℕ, let Sℓ(v)=∑w∈ N(v)ℓ(w). The additive number η(G) is the least k for which there exists ℓ:V(G)→[k] such that Sℓ(u)≠ Sℓ(v) for every uv∈ E(G), while the list additive number ηℓ(G) is the least k such that the same condition can be satisfied from every assignment of k-element lists L(v)⊂ℕ with ℓ(v)∈ L(v). We show that for every k≥2, there is a graph G with η(G)=1 and ηℓ(G)≥ k. The separation persists at the minimum possible ordinary value for positive-degree regular graphs: there is a regular graph H with η(H)=2 and ηℓ(H)≥ k. We also determine a sharp lower bound for η(G) in terms of the order and minimum degree of G, and show that the unbounded list gap persists at asymptotically extremal density. Finally, for every fixed k≥2, it is NP-hard to distinguish η(G)=2 from η(G)>k, even on asymptotically extremal dense graphs. Consequently, η(G) admits no polynomial-time constant-factor approximation unless P=NP. Together, these results reveal a robust gap phenomenon: the separation between ordinary and list additive labeling persists at the smallest possible ordinary values and even under asymptotically extremal density, while the ordinary parameter itself remains hard to approximate.
Related
BibTeX
@misc{ahadi2026extremal,
title = {{Extremal List Gaps and Inapproximability in Additive Graph Labeling}},
author = {Arash Ahadi and Sharareh Alipour},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12234},
eprint = {2609.12234},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12234},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extremal List Gaps and Inapproximability in Additive Graph Labeling
AU - Arash Ahadi
AU - Sharareh Alipour
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.12234
UR - https://arxiv.org/abs/2609.12234
AB - We study a vertex-labeling analogue of the $1−2−3$ problem and its list version. For a labeling ℓ:V(G)→ℕ, let S_ℓ(v)=∑_w∈ N(v)ℓ(w). The additive number η(G) is the least k for which there exists ℓ:V(G)→[k] such that S_ℓ(u)≠ S_ℓ(v) for every uv∈ E(G), while the list additive number η_ℓ(G) is the least k such that the same condition can be satisfied from every assignment of k-element lists L(v)⊂ℕ with ℓ(v)∈ L(v). We show that for every k≥2, there is a graph G with η(G)=1 and η_ℓ(G)≥ k. The separation persists at the minimum possible ordinary value for positive-degree regular graphs: there is a regular graph H with η(H)=2 and η_ℓ(H)≥ k. We also determine a sharp lower bound for η(G) in terms of the order and minimum degree of G, and show that the unbounded list gap persists at asymptotically extremal density. Finally, for every fixed k≥2, it is NP-hard to distinguish η(G)=2 from η(G)>k, even on asymptotically extremal dense graphs. Consequently, η(G) admits no polynomial-time constant-factor approximation unless P=NP. Together, these results reveal a robust gap phenomenon: the separation between ordinary and list additive labeling persists at the smallest possible ordinary values and even under asymptotically extremal density, while the ordinary parameter itself remains hard to approximate.
ER -