• 1
  • 1
  • 2
  • 6
  • 5
  • 6
  • 3
  • 4
IPM
30
YEARS OLD

“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16353
School of Mathematics
  Title:   Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
  Author(s): 
1.  Mohammadreza Bidgoli
2.  Behruz Tayfeh-Rezaie (Joint with A. Mohammadian)
  Status:   To Appear
  Journal: European J. Combin.
  Supported by:  IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right