The clique number of the exact distance t-power graph: complexity and eigenvalue bounds

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Downloads (Pure)

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-2Engels
Pagina's (van-tot)55-70
Aantal pagina's16
TijdschriftDiscrete Applied Mathematics
Volume363
Vroegere onlinedatum6 dec. 2024
DOI's
StatusE-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 .

FinanciersFinanciernummer
Nederlandse Organisatie voor Wetenschappelijk OnderzoekVI.Vidi.213.085

    Vingerafdruk

    Duik in de onderzoeksthema's van 'The clique number of the exact distance t-power graph: complexity and eigenvalue bounds'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit