Spectral upper bound on the quantum k-independence number of a graph

Aida Abiad, Clive Elphick, Pawel Wocjan

Research output: Contribution to journalArticlepeer-review


A well-known upper bound for the independence number α(G) of a graph G, due to Cvetković, is that α(G) ≤ n 0 + min{n +, n }, where (n +, n 0, n ) is the inertia of G. We prove that this bound is also an upper bound for the quantum independence number α q(G), where α q(G) ≥ α(G) and for some graphs α q(G) ≫ α(G). We identify numerous graphs for which α(G) = α q(G), thus increasing the number of graphs for which α q is known. We also demonstrate that there are graphs for which the above bound is not exact with any Hermitian weight matrix, for α(G) and α q(G). Finally, we show this result in the more general context of spectral bounds for the quantum k-independence number, where the k-independence number is the maximum size of a set of vertices at pairwise distance greater than k.

Original languageEnglish
Pages (from-to)331-338
Number of pages8
JournalThe Electronic Journal of Linear Algebra
Publication statusPublished - 2022

Cite this