Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs

DOI10.1016/J.EJC.2020.103256MaRDI QIDQ2225448zbMATH OpenOpenAlexFDO

Authors Mohammadreza Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.01942

Hamming graphs percolation triangular graph

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: For any integer

r g e q s l a n t 0

, 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 (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, we show that

m (K_{n}^{d}, r) = f r a c 1 + o (1) (d + 1)! r^{d}

when both

r

and

d

go to infinity with

r < n

and

d = o (! s q r t r)

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225448)