The clique number of the exact distance $t$-power graph: complexity and eigenvalue bounds
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916479643942912 |
|---|---|
| author | Abiad, Aida Ameli, Afrouz Jabal Reijnders, Luuk |
| author_facet | Abiad, Aida Ameli, Afrouz Jabal Reijnders, Luuk |
| contents | The exact distance $t$-power of a graph $G$, $G^{[\sharp t]}$, is a graph which has the same vertex set as $G$, with two vertices adjacent in $G^{[\sharp t]}$ if and only if they are at distance exactly $t$ in the original graph $G$. We study the clique number of this graph, also known as the $t$-equidistant number. We show that it is NP-hard to determine the $t$-equidistant number of a graph, and that in fact, it is NP-hard to approximate it within a constant factor. We also investigate how the $t$-equidistant number relates to another distance-based graph parameter; the $t$-independence number. In particular, we show how large the gap between both parameters can be. The hardness results motivate deriving eigenvalue bounds, which compare well against a known general bound. In addition, the tightness of the proposed eigenvalue bounds is studied. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00189 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The clique number of the exact distance $t$-power graph: complexity and eigenvalue bounds Abiad, Aida Ameli, Afrouz Jabal Reijnders, Luuk Combinatorics The exact distance $t$-power of a graph $G$, $G^{[\sharp t]}$, is a graph which has the same vertex set as $G$, with two vertices adjacent in $G^{[\sharp t]}$ if and only if they are at distance exactly $t$ in the original graph $G$. We study the clique number of this graph, also known as the $t$-equidistant number. We show that it is NP-hard to determine the $t$-equidistant number of a graph, and that in fact, it is NP-hard to approximate it within a constant factor. We also investigate how the $t$-equidistant number relates to another distance-based graph parameter; the $t$-independence number. In particular, we show how large the gap between both parameters can be. The hardness results motivate deriving eigenvalue bounds, which compare well against a known general bound. In addition, the tightness of the proposed eigenvalue bounds is studied. |
| title | The clique number of the exact distance $t$-power graph: complexity and eigenvalue bounds |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.00189 |