“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16353  


Abstract:  
The rneighbor bootstrap percolation on a graph is an activation process of the vertices. The process starts with some initially activated vertices and then, in each round, any inactive vertex with at least r active neighbors becomes activated.
A set of initially activated vertices leading to the activation of all vertices is said to be a percolating set.
Denote the minimum size of a percolating set in the rneighbor bootstrap percolation process on a graph G by m(G, r). In this paper, we present upper and lower bounds
on m(K_{n}^{d}, r), where K_{n}^{d} is the Cartesian product of d copies of the complete graph K_{n} which is referred as the Hamming graph.
Among other results, when d goes to infinity, we show that m(K_{n}^{d}, r)=[(1+o(1))/((d+1)!)]r^{d} if r >> d^{2} and n\geqslant r+1.
Furthermore, we explicitly determine m(L(K_{n}), r), where L(K_{n}) is the line graph of K_{n} also known as triangular graph. Download TeX format 

back to top 