On the \(P_3\)-hull number of Kneser graphs (Q2048567): Difference between revisions

Summary: 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\geqslant 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.