“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16353 |
|
||||
| Abstract: | |||||
|
The r-neighbor 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 r-neighbor bootstrap percolation process on a graph G by m(G, r). In this paper, we present upper and lower bounds
on m(Knd, r), where Knd is the Cartesian product of d copies of the complete graph Kn which is referred as the Hamming graph.
Among other results, when d goes to infinity, we show that m(Knd, r)=[(1+o(1))/((d+1)!)]rd if r >> d2 and n\geqslant r+1.
Furthermore, we explicitly determine m(L(Kn), r), where L(Kn) is the line graph of Kn also known as triangular graph.
Download TeX format |
|||||
| back to top | |||||
