Maximal induced paths and minimal percolating sets in hypercubes

Abstract

For a graph $G$, the \emph{$r$-bootstrap percolation} process can be described as follows: Start with an initial set $A$ of "infected'' vertices. Infect any vertex with at least $r$ infected neighbours, and continue this process until no new vertices can be infected. $A$ is said to \emph{percolate in $G$} if eventually all the vertices of $G$ are infected. $A$ is a \emph{minimal percolating set} in $G$ if $A$ percolates in $G$ and no proper subset of $A$ percolates in $G$. An induced path, $P$, in a hypercube $Q_n$ is maximal if no induced path in $Q_n$ properly contains $P$. Induced paths in hypercubes are also called snakes. We study the relationship between maximal snakes and minimal percolating sets (under 2-bootstrap percolation) in hypercubes. In particular, we show that every maximal snake contains a minimal percolating set, and that every minimal percolating set is contained in a maximal snake.

Keywords

• -

References

1. D. Kinny. A new approach to the snake-in-the-box problem., in Proceedings of the 20th European Conference on Artificial Intelligence, ECAI-2012, 462-467, 2012.
2. Dayanand S. Rajan and Anil M. Shende. Maximal and reversible snakes in hypercubes, in 24th Annual Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, 1999.
3. Eric Riedl. Largest and smallest minimal percolating sets in trees, The Electronic Journal of Combi- natorics, 19, 2010.
4. Eric Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation, The Electronic Journal of Combinatorics, 17, 2010.
5. W. H. Kautz, Unit distance error checking codes, in IRE Transaction on Electronic Computers, 7, 179–180, 1958.