The inapproximability for the $0,1$-additive numberReport as inadecuate




The inapproximability for the $0,1$-additive number - Download this document for free, or read online. Document in PDF available to download.

1 Sharif University of Technology 2 Carleton University

Abstract : An additive labeling of a graph $G$ is a function $\ell :VG ightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma {w \sim v} \ell w eq \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 : VG ightarrow \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$, $\etaG= \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 - \etaG \geq k$. A $0,1$-additive labeling of a graph $G$ is a function $\ell :VG ightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma {w \sim v} \ell w eq \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.

Keywords : 0 1-additive labeling Additive labeling additive number lucky number 1-additive number Computational complexity





Author: Arash Ahadi - Ali Dehghan -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents