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

Abstract : An 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$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\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 in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(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$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (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 $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ 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 $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.217-226
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352839
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 17:39:33
Dernière modification le : jeudi 7 septembre 2017 - 01:03:49
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:24:13

Fichier

2366-9946-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352839, version 1

Collections

Citation

Arash Ahadi, Ali Dehghan. The inapproximability for the $(0,1)$-additive number. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.217-226. 〈hal-01352839〉

Partager

Métriques

Consultations de la notice

30

Téléchargements de fichiers

125