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 $\ell :V(G)\to \mathbb{N}$, let $S_{\ell }(v)={\sum }_{w\in N(v)}\ell (w)$. The additive number $\eta (G)$ is the least $k$ for which there exists $\ell :V(G)\to [k]$ such that $S_{\ell }(u)\ne S_{\ell }(v)$ for every $uv\in E(G)$, while the list additive number ${\eta }_{\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 $\ell (v)\in L(v)$. We show that for every $k\ge 2$, there is a graph $G$ with $\eta (G)=1$ and ${\eta }_{\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 }_{\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{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.