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