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

*Arash Ahadi, Ali Dehghan*

#### Abstract

An

*additive labeling*of a graph G is a function ℓ:V(G) →N, such that for every two adjacent vertices v and u of G , ∑_{w ∼v}ℓ(w)≠∑_{w ∼u}ℓ(w) ( x ∼y means that x is joined to y). The*additive number*of G , denoted by η(G), is the minimum number k such that G has a additive labeling ℓ:V(G) →N_{k}. The*additive choosability*of a graph G, denoted by η_{ℓ}(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 in his PhD thesis conjectured that for every graph G, η(G)= η_{ℓ}(G). We give a negative answer to this conjecture and we show that for every k there is a graph G such that η_{ℓ}(G)- η(G) ≥k. A*(0,1)-additive labeling*of a graph G is a function ℓ:V(G) →{0,1}, such that for every two adjacent vertices v and u of G , ∑_{w ∼v}ℓ(w)≠∑_{w ∼u}ℓ(w) . A graph may lack any (0,1)-additive labeling. We show that it is 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_{ℓ∈Γ}∑_{v∈V(G)}ℓ(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 ɛ>0 , approximating the (0,1)-additive number within n^{1-ɛ}is NP -hard.Full Text: PDF PostScript