The inapproximability for the (0,1)-additive number

An {\it additive labeling} of a graph $G$ is a function $\ell :V(G) \rightarrow\mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\sum_{w \sim v}\ell(w)\neq \sum_{w \sim u}\ell(w)$ ($x \sim y$ means that $x$ is joined to $y$). The {\it additive number} of $G$, denoted by $η(G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell :V(G) \rightarrow \mathbb{N}_k$. The {\it additive choosability} of a graph $G$, denoted by $η_{\ell}(G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone (2012) \cite{a80} conjectured that for every graph $G$, $η(G)= η_{\ell}(G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $η_{\ell}(G)- η(G) \geq k$. A {\it $(0,1)$-additive labeling} of a graph $G$ is a function $\ell :V(G) \rightarrow\{0,1\}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\sum_{w \sim v}\ell(w)\neq \sum_{w \sim u}\ell(w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is $\mathbf{NP}$-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $σ_{1} (G) = \min_{\ell \in Γ}\sum_{v\in V(G)}\ell(v)$ where $Γ$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\varepsilon >0$, approximating the $(0,1)$-additive number within $n^{1-\varepsilon}$ is $\mathbf{NP}$-hard.

No reviews yet.

No comments yet.