Extremal List Gaps and Inapproximability in Additive Graph Labeling

We study a vertex-labeling analogue of the $1$-$2$-$3$ problem and its list version. For a labeling $\mathrm{\ell }:V(G)\to \mathbb{N}$, let $S_{\mathrm{\ell }}(v)={\sum }_{w\in N(v)}\mathrm{\ell }(w)$. The additive number $\eta (G)$ is the least $k$ for which there exists $\mathrm{\ell }:V(G)\to [k]$ such that $S_{\mathrm{\ell }}(u)\mathrm{\ne }{S}_{\mathrm{\ell }}(v)$ for every $uv\in E(G)$, while the list additive number ${\eta }_{\mathrm{\ell }}(G)$ is the least $k$ such that the same condition can be satisfied from every assignment of $k$-element lists $L(v)\subset \mathbb{N}$ with $\mathrm{\ell }(v)\in L(v)$. We show that for every $k\ge 2$, there is a graph $G$ with $\eta (G)=1$ and ${\eta }_{\mathrm{\ell }}(G)\ge k$. The separation persists at the minimum possible ordinary value for positive-degree regular graphs: there is a regular graph $H$ with $\eta (H)=2$ and ${\eta }_{\mathrm{\ell }}(H)\ge k$. We also determine a sharp lower bound for $\eta (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\ge 2$, it is NP-hard to distinguish $\eta (G)=2$ from $\eta (G)>k$, even on asymptotically extremal dense graphs. Consequently, $\eta (G)$ admits no polynomial-time constant-factor approximation unless $\mathrm{P}=\mathrm{N}\mathrm{P}$. 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.