Artículo
On the p3-hull number of kneser graphs
Grippo, Luciano Norberto
; Pastine, Adrián Gabriel; Torres, Pablo Daniel
; Valencia Pabon, Mario; Vera, Juan C.
Fecha de publicación:
07/2021
Editorial:
Electronic Journal Of Combinatorics
Revista:
Electronic Journal Of Combinatorics, The
ISSN:
1077-8926
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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.
Palabras clave:
Kneser graphs
,
Hull convexity
,
Hull sets
,
Disease spread problems
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(IMASL)
Articulos de INST. DE MATEMATICA APLICADA DE SAN LUIS
Articulos de INST. DE MATEMATICA APLICADA DE SAN LUIS
Citación
Grippo, Luciano Norberto; Pastine, Adrián Gabriel; Torres, Pablo Daniel; Valencia Pabon, Mario; Vera, Juan C.; On the p3-hull number of kneser graphs; Electronic Journal Of Combinatorics; Electronic Journal Of Combinatorics, The; 28; 3; 7-2021; 1-9
Compartir
Altmétricas