On the P3-hull number of Kneser graphs
Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina.
| Autores principales: | , , , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
The Electronic Journal of Combinatorics
2024
|
| Materias: | |
| Acceso en línea: | http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1585 |
| Aporte de: |
| id |
I71-R177-UNGS-1585 |
|---|---|
| record_format |
dspace |
| spelling |
I71-R177-UNGS-15852024-12-09T18:33:19Z On the P3-hull number of Kneser graphs Grippo, Luciano Norberto Pastine, Adrián Torres, Pablo Daniel Valencia-Pabon, Mario Vera, Juan C. Kneser Graphs P_3-Convexity P_3-Hull Number Hull convexity Hull sets Disease spread problems Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Pastine, Adrián. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Pastine, Adrián Gabriel. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - San Luis; Argentina. Fil: Valencia Pabon, Mario. Universite de Paris 1 - Pantheon Sorbonne; Francia. Fil: Vera, Juan C. Tilburg School of Economics and Management; Países Bajos. 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. 2024-07-16T17:07:07Z 2024-07-16T17:07:07Z 2021 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Grippo, L. N. et al. (7-2021). On the P3-hull number of Kneser graphs. The Electronic Journal of Combinatorics, 28(3), 3-32. 1077-8926 http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1585 eng https://doi.org/10.37236/9903 info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf application/pdf The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics. 7-2021; 28(3): 3-32 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i3p32/pdf |
| institution |
Universidad Nacional de General Sarmiento |
| institution_str |
I-71 |
| repository_str |
R-177 |
| collection |
Repositorio Institucional Digital de Acceso Abierto (UNGS) |
| language |
Inglés |
| orig_language_str_mv |
eng |
| topic |
Kneser Graphs P_3-Convexity P_3-Hull Number Hull convexity Hull sets Disease spread problems |
| spellingShingle |
Kneser Graphs P_3-Convexity P_3-Hull Number Hull convexity Hull sets Disease spread problems Grippo, Luciano Norberto Pastine, Adrián Torres, Pablo Daniel Valencia-Pabon, Mario Vera, Juan C. On the P3-hull number of Kneser graphs |
| topic_facet |
Kneser Graphs P_3-Convexity P_3-Hull Number Hull convexity Hull sets Disease spread problems |
| description |
Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. |
| format |
Artículo Artículo publishedVersion |
| author |
Grippo, Luciano Norberto Pastine, Adrián Torres, Pablo Daniel Valencia-Pabon, Mario Vera, Juan C. |
| author_facet |
Grippo, Luciano Norberto Pastine, Adrián Torres, Pablo Daniel Valencia-Pabon, Mario Vera, Juan C. |
| author_sort |
Grippo, Luciano Norberto |
| title |
On the P3-hull number of Kneser graphs |
| title_short |
On the P3-hull number of Kneser graphs |
| title_full |
On the P3-hull number of Kneser graphs |
| title_fullStr |
On the P3-hull number of Kneser graphs |
| title_full_unstemmed |
On the P3-hull number of Kneser graphs |
| title_sort |
on the p3-hull number of kneser graphs |
| publisher |
The Electronic Journal of Combinatorics |
| publishDate |
2024 |
| url |
http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1585 |
| work_keys_str_mv |
AT grippolucianonorberto onthep3hullnumberofknesergraphs AT pastineadrian onthep3hullnumberofknesergraphs AT torrespablodaniel onthep3hullnumberofknesergraphs AT valenciapabonmario onthep3hullnumberofknesergraphs AT verajuanc onthep3hullnumberofknesergraphs |
| _version_ |
1824528734454022144 |