{"id":"arxiv/2609.12234","url":"https://arxiv.org/abs/2609.12234","tags":["math.CO"],"score":0,"title":"Extremal List Gaps and Inapproximability in Additive Graph Labeling","domain":"math.CO","source":"arxiv","authors":["Arash Ahadi","Sharareh Alipour"],"reviews":0,"subject":"math.CO","summary":"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 $η(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 $η_\\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\\ge2$, there is a graph $G$ with $η(G)=1$ and $η_\\ell(G)\\ge k$. The…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}