Geodesic
On the \(P_3\)-hull number of Kneser graphs
The electronic journal of combinatorics, Tome 28 (2021) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/9903
Classification : 05C76, 52A37, 05C85
Mots-clés : infection spreading in a graph, Kneser graph

Luciano N. Grippo  1   ; Adrián Pastine    ; Pablo Torres    ; Mario Valencia-Pabon    ; Juan C. Vera 

1 UNGS 
@article{10_37236_9903,
     author = {Luciano N. Grippo and Adri\'an Pastine and Pablo Torres and Mario Valencia-Pabon and Juan C. Vera},
     title = {On the {\(P_3\)-hull} number of {Kneser} graphs},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {3},
     doi = {10.37236/9903},
     zbl = {1470.05138},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9903/}
}
TY  - JOUR
AU  - Luciano N. Grippo
AU  - Adrián Pastine
AU  - Pablo Torres
AU  - Mario Valencia-Pabon
AU  - Juan C. Vera
TI  - On the \(P_3\)-hull number of Kneser graphs
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9903/
DO  - 10.37236/9903
ID  - 10_37236_9903
ER  - 
%0 Journal Article
%A Luciano N. Grippo
%A Adrián Pastine
%A Pablo Torres
%A Mario Valencia-Pabon
%A Juan C. Vera
%T On the \(P_3\)-hull number of Kneser graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9903/
%R 10.37236/9903
%F 10_37236_9903
Luciano N. Grippo; Adrián Pastine; Pablo Torres; Mario Valencia-Pabon; Juan C. Vera. On the \(P_3\)-hull number of Kneser graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9903

Cité par Sources :