On the P₃ -hull numbers of q -Kneser graphs and Grassmann graphs

Abstract: Let

S

be an

n

-dimensional vector space over the finite field

m a t h b b F_{q}

, where

q

is necessarily a prime power. Denote

K_{q} (n, k)

(resp.

J_{q} (n, k)

) to be the emph{

q

-Kneser graph} (resp. emph{Grassmann graph}) for

k g e q 1

whose vertices are the

k

-dimensional subspaces of

S

and two vertices

v_{1}

and

v_{2}

are adjacent if

d i m (v_{1} c a p v_{2}) = 0

(resp.

d i m (v_{1} c a p v_{2}) = k - 1

). We consider the infection spreading in the

q

-Kneser graphs and the Grassmann graphs: a vertex gets infected if it has at least two infected neighbors. In this paper, we compute the

P_{3}

-hull numbers of

K_{q} (n, k)

and

J_{q} (n, k)

respectively, which is the minimum size of a vertex set that eventually infects the whole graph.

This page was built for publication: On the $ P_3 $-hull numbers of $ q $-Kneser graphs and Grassmann graphs