Loading [MathJax]/jax/output/HTML-CSS/jax.js

Arash Ahadi ; Ali Dehghan - The inapproximability for the (0,1)-additive number

dmtcs:2145 - Discrete Mathematics & Theoretical Computer Science, June 17, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2145
The inapproximability for the (0,1)-additive numberArticle

Authors: Arash Ahadi 1; Ali Dehghan 2,3

An <i>additive labeling</i> of a graph G is a function :V(G)N, such that for every two adjacent vertices v and u of G, Σwv(w)Σwu(w) (xy 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)-<i>additive labeling</i> of a graph G is a function :V(G){0,1}, such that for every two adjacent vertices v and u of G, Σwv(w)Σwu(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ΓΣvV(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.


Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: June 17, 2016
Submitted on: April 27, 2013
Keywords: (0,1)-additive labeling,Additive labeling, additive number, lucky number,1)-additive number, Computational complexity,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 512 times.
This article's PDF has been downloaded 1022 times.