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

Aida Abiad Monge; Luuk E.R.M. Reijnders; Afrouz Jabal Ameli

doi:10.1016/j.dam.2024.11.032

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

Aida Abiad Monge (Corresponding author), Luuk E.R.M. Reijnders, Afrouz Jabal Ameli

Research output: Contribution to journal › Article › Academic › peer-review

34 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	55-70
Number of pages	16
Journal	Discrete Applied Mathematics
Volume	363
Early online date	6 Dec 2024
DOIs	https://doi.org/10.1016/j.dam.2024.11.032
Publication status	Published - 15 Mar 2025

Funding

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 .

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	VI.Vidi.213.085

Keywords

Clique number
Complexity
Eigenvalue bounds
Exact distance graph power

Access to Document

10.1016/j.dam.2024.11.032

pdfFinal published version, 554 KBLicence: CC BY

Cite this

@article{99a94f4e8dcf4636acbb9e471cf2b422,

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

abstract = "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.",

keywords = "Clique number, Complexity, Eigenvalue bounds, Exact distance graph power",

author = "{Abiad Monge}, Aida and Reijnders, {Luuk E.R.M.} and {Jabal Ameli}, Afrouz",

year = "2025",

month = mar,

day = "15",

doi = "10.1016/j.dam.2024.11.032",

language = "English",

volume = "363",

pages = "55--70",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The clique number of the exact distance t-power graph

T2 - complexity and eigenvalue bounds

AU - Abiad Monge, Aida

AU - Reijnders, Luuk E.R.M.

AU - Jabal Ameli, Afrouz

PY - 2025/3/15

Y1 - 2025/3/15

N2 - 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.

AB - 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.

KW - Clique number

KW - Complexity

KW - Eigenvalue bounds

KW - Exact distance graph power

UR - http://www.scopus.com/inward/record.url?scp=85211111073&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2024.11.032

DO - 10.1016/j.dam.2024.11.032

M3 - Article

SN - 0166-218X

VL - 363

SP - 55

EP - 70

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this