On the $P_3$-hull numbers of $q$-Kneser graphs and Grassmann graphs

Abstract

Let $S$ be an $n$-dimensional vector space over the finite field ${\mathbb{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\ge 1$ whose vertices are the $k$-dimensional subspaces of $S$ and two vertices $v_1$ and $v_2$ are adjacent if $\dim (v_1\cap v_2)=0$ (resp. $\dim (v_1\cap 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.