On the \(P_3\)-hull number of Kneser graphs
type: Item
instance of: scholarly article
title: On the \(P_3\)-hull number of Kneser graphs
zbMATH Open document ID: 1470.05138
DOI: 10.37236/9903
author: Luciano N. Grippo
author: Adrián Pastine
author: P. Torres
author: Mario Valencia-Pabon
author: Juan Vera
published in: The Electronic Journal of Combinatorics
publication date: 2021-08-09T00:00:00Z
review text: Summary: 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\geqslant 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.
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 7379576
zbMATH Keywords: infection spreading in a graph
zbMATH Keywords: Kneser graph
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/9903
OpenAlex ID: W3191386063
cites work: Graphs with intrinsic s3 convexities
cites work: On the Carathéodory Number for the Convexity of Paths of Order Three
cites work: On slowly percolating sets of minimal size in bootstrap percolation
cites work: The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
cites work: Q5393667
cites work: Grundy domination and zero forcing in Kneser graphs
cites work: On the \(P_3\)-hull number of Hamming graphs
cites work: Some Elementary Properties of Interval Convexities
cites work: Q5396751
cites work: Geodetic number versus hull number in \(P_3\)-convexity
cites work: Convexities related to path properties on graphs
cites work: On the Approximability of Influence in Social Networks
cites work: Inapproximability results for graph convexity parameters
cites work: Complexity results related to monophonic convexity
cites work: An upper bound on the \(P_3\)-Radon number
cites work: Q3787039
cites work: Convex sets in graphs. II: Minimal path convexity
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Q2716030
cites work: Explicit 2-factorizations of the odd graph
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: The maximum time of 2-neighbor bootstrap percolation: complexity results
cites work: Minimal percolating sets in bootstrap percolation
cites work: Geodesic Convexity in Graphs
cites work: Maximal percolation time in hypercubes under 2-bootstrap percolation
cites work: Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
cites work: On the diameter of Kneser graphs
description: scientific article; zbMATH DE number 7379576