On the $P_3$-Hull Number of Kneser Graphs

Abstract

This paper considers an infection spreading in a graph; a vertex gets infected if at least two of its neighbors are infected. The $P_3$-hull number is the minimum size of a vertex set that eventually infects the whole graph.

In the specific case of the Kneser graph $K(n,k)$, with $n\ge 2k+1$, an infection spreading on the family of $k$-sets of an $n$-set is considered. A set is infected whenever two sets disjoint from it are infected. We compute the exact value of the $P_3$-hull number of $K(n,k)$ for $n>2k+1$. For $n = 2k+1$, using graph homomorphisms from the Knesser graph to the Hypercube, we give lower and upper bounds.