2019/10/16 by Paweł Wocjan, Wocjan, Pawel, Clive Elphick +3
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1910.07339
openalex publication_date 2019/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A well known upper bound for the independence number α(G) of a graph G, due to Cvetković, is that α(G) ≤ n0 + min\n+ , n-\ where (n+, n0, 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.