On the characterization of graphs with tree 3-spanners
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910816687620096 |
|---|---|
| author | Lin, Lan Lin, Yixun |
| author_facet | Lin, Lan Lin, Yixun |
| contents | The tree spanner problem for a graph $G$ is as follows: For a given integer $k$, is there a spanning tree $T$ of $G$ (called a tree $k$-spanner) such that the distance in $T$ between every pair of vertices is at most $k$ times their distance in $G$? The minimum $k$ that $G$ admits a tree $k$-spanner is denoted by $σ(G)$. It is well known in the literature that determining $σ(G)\leq 2$ is polynomially solvable, while determining $σ(G)\leq k$ for $k\geq 4$ is NP-complete. A long-standing open problem is to characterize graphs with $σ(G)=3$. This paper settles this open problem by proving that it is polynomially solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03741 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the characterization of graphs with tree 3-spanners Lin, Lan Lin, Yixun Combinatorics 05C35, 05C05, 90C27 G.2.1; G.2.2 The tree spanner problem for a graph $G$ is as follows: For a given integer $k$, is there a spanning tree $T$ of $G$ (called a tree $k$-spanner) such that the distance in $T$ between every pair of vertices is at most $k$ times their distance in $G$? The minimum $k$ that $G$ admits a tree $k$-spanner is denoted by $σ(G)$. It is well known in the literature that determining $σ(G)\leq 2$ is polynomially solvable, while determining $σ(G)\leq k$ for $k\geq 4$ is NP-complete. A long-standing open problem is to characterize graphs with $σ(G)=3$. This paper settles this open problem by proving that it is polynomially solvable. |
| title | On the characterization of graphs with tree 3-spanners |
| topic | Combinatorics 05C35, 05C05, 90C27 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2502.03741 |