TY - JOUR
T1 - On the p3-hull number of kneser graphs
AU - Grippo, Luciano N.
AU - Pastine, Adrián
AU - Torres, Pablo
AU - Valencia-Pabon, Mario
AU - Vera, Juan C.
PY - 2021/7
Y1 - 2021/7
N2 - This paper considers an infection spreading in a graph; a vertex gets infected if at least two of its neighbors are infected. The P3-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 ≥ 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 P3-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. Mathematics Subject Classifications: 05C76, 52A37, 05C85.
AB - This paper considers an infection spreading in a graph; a vertex gets infected if at least two of its neighbors are infected. The P3-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 ≥ 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 P3-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. Mathematics Subject Classifications: 05C76, 52A37, 05C85.
U2 - 10.37236/9903
DO - 10.37236/9903
M3 - Article
AN - SCOPUS:85111356216
SN - 1097-1440
VL - 28
JO - The Electronic Journal of Combinatorics: EJC
JF - The Electronic Journal of Combinatorics: EJC
IS - 3
M1 - P3.32
ER -