Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

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) →Nk. 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 n1-ɛ is NP -hard.

Full Text: PDF PostScript