Treewidth of the q-Kneser graphs

Abstract: Let

V

be an

n

-dimensional vector space over a finite field

m a t h b b F_{q}

, where

q

is a prime power. Define the emph{generalized

q

-Kneser graph}

K_{q} (n, k, t)

to be the graph whose vertices are the

k

-dimensional subspaces of

V

and two vertices

F_{1}

and

F_{2}

are adjacent if

d i m (F_{1} c a p F_{2}) < t

. Then

K_{q} (n, k, 1)

is the well-known

q

-Kneser graph. In this paper, we determine the treewidth of

K_{q} (n, k, t)

for

n g e q 2 t (k - t + 1) + k + 1

and

t g e 1

exactly. Note that

K_{q} (n, k, k - 1)

is the complement of the Grassmann graph

G_{q} (n, k)

. We give a more precise result for the treewidth of

o v e r l i n e G_{q} (n, k)

for any possible

n

,

k

and

q

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Treewidth of the \(q\)-Kneser graphs