Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1903.11933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916238226096128 |
|---|---|
| author | Claverol, Mercè García, Alfredo Hernández, Greogorio Hernando, Carmen Maureso, Montserrat Mora, Mercè Tejel, Javier |
| author_facet | Claverol, Mercè García, Alfredo Hernández, Greogorio Hernando, Carmen Maureso, Montserrat Mora, Mercè Tejel, Javier |
| contents | In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $β(G)$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $2\le β(G) \le \lceil \frac{2n}{5}\rceil$ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of $G$ is 2 and to build a resolving set of size $\lceil \frac{2n}{5}\rceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_11933 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Metric dimension of maximal outerplanar graphs Claverol, Mercè García, Alfredo Hernández, Greogorio Hernando, Carmen Maureso, Montserrat Mora, Mercè Tejel, Javier Combinatorics 05C12, 05C62 In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $β(G)$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $2\le β(G) \le \lceil \frac{2n}{5}\rceil$ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of $G$ is 2 and to build a resolving set of size $\lceil \frac{2n}{5}\rceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2. |
| title | Metric dimension of maximal outerplanar graphs |
| topic | Combinatorics 05C12, 05C62 |
| url | https://arxiv.org/abs/1903.11933 |