Samenvatting
The exact distance t-power of a graph G, G [♯t], is a graph which has the same vertex set as G, with two vertices adjacent in G [♯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.
Originele taal-2 | Engels |
---|---|
Pagina's (van-tot) | 55-70 |
Aantal pagina's | 16 |
Tijdschrift | Discrete Applied Mathematics |
Volume | 363 |
Vroegere onlinedatum | 6 dec. 2024 |
DOI's | |
Status | E-publicatie vóór gedrukte publicatie - 6 dec. 2024 |
Financiering
The authors thank James Tuite for bringing the equidistant number to their attention, Sjanne Zeijlemaker for helping with the LP from Appendix A.2 , and Frits Spieksma for useful discussions on Section 2 . Aida Abiad is supported by the D utch Research Council through the grant VI.Vidi.213.085 .
Financiers | Financiernummer |
---|---|
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | VI.Vidi.213.085 |