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

Abstract: A well known upper bound for the independence number

a l p h a (G)

of a graph

G

, due to Cvetkovi'{c}, is that �egin{equation*} alpha(G) le n^0 + min{n^+ , n^-} end{equation*} 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

a l p h a_{q}

(G), where

a l p h a_{q} (G) g e a l p h a (G)

and for some graphs

a l p h a_{q} (G) g g a l p h a (G)

. We identify numerous graphs for which

a l p h a (G) = a l p h a_{q} (G)

, thus increasing the number of graphs for which

a l p h a_{q}

is known. We also demonstrate that there are graphs for which the above bound is not exact with any Hermitian weight matrix, for

a l p h a (G)

and

a l p h a_{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

.

Full work available at URL: https://arxiv.org/abs/1910.07339

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (8)

This page was built for publication: Spectral upper bound on the quantum \(k\)-independence number of a graph