On the $P3$-hull number of Kneser graphs

GRIPPO, L.N.; ADRIÁN PASTINE; PABLO TORRES; MARIO VALENCIA-PABÓN; JUAN C. VERA

ELECTRONIC JOURNAL OF COMBINATORICS, THE

ELECTRONIC JOURNAL OF COMBINATORICS

Lugar: Pensilvania; Año: 2021 vol. 28

1077-8926

This paper considers an infection spreading in a graph; a vertex gets infected ifat least two of its neighbors are infected. The $P_3$-hull number is the minimum sizeof a vertex set that eventually infects the whole graph.In the specific case of the Kneser graph $K(n, k)$, with $n>2k+ 1$, an infectionspreading on the family of $k$-sets of ann-set is considered. A set is infected whenevertwo sets disjoint from it are infected. We compute the exact value of the $P_3$-hullnumber of $K(n, k)$ for $n >2k+ 1$. For $n= 2k+ 1$, using graph homomorphismsfrom the Knesser graph to the Hypercube, we give lower and upper bounds.