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

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\geq 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.

No reviews yet.

No comments yet.