The inapproximability for the $(0,1)$-additive number
An <i>additive labeling</i> 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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2145/pdf |
| _version_ | 1797270096869064704 |
|---|---|
| author | Arash Ahadi Ali Dehghan |
| author_facet | Arash Ahadi Ali Dehghan |
| author_sort | Arash Ahadi |
| collection | DOAJ |
| description | An <i>additive labeling</i> 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)$-<i>additive labeling</i> 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. |
| first_indexed | 2024-04-25T01:58:51Z |
| format | Article |
| id | doaj.art-b9a859381b174f5ea7d80d6a73579706 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:51Z |
| publishDate | 2016-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b9a859381b174f5ea7d80d6a735797062024-03-07T15:29:03ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-06-01Vol. 17 no. 3Graph Theory10.46298/dmtcs.21452145The inapproximability for the $(0,1)$-additive numberArash Ahadi0Ali Dehghan1Sharif University of Technology [Tehran]Carleton UniversityAn <i>additive labeling</i> 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)$-<i>additive labeling</i> 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.https://dmtcs.episciences.org/2145/pdf(01)-additive labelingadditive labelingadditive numberlucky number1)-additive numbercomputational complexity[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Arash Ahadi Ali Dehghan The inapproximability for the $(0,1)$-additive number Discrete Mathematics & Theoretical Computer Science (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] |
| title | The inapproximability for the $(0,1)$-additive number |
| title_full | The inapproximability for the $(0,1)$-additive number |
| title_fullStr | The inapproximability for the $(0,1)$-additive number |
| title_full_unstemmed | The inapproximability for the $(0,1)$-additive number |
| title_short | The inapproximability for the $(0,1)$-additive number |
| title_sort | inapproximability for the 0 1 additive number |
| topic | (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] |
| url | https://dmtcs.episciences.org/2145/pdf |
| work_keys_str_mv | AT arashahadi theinapproximabilityforthe01additivenumber AT alidehghan theinapproximabilityforthe01additivenumber AT arashahadi inapproximabilityforthe01additivenumber AT alidehghan inapproximabilityforthe01additivenumber |