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
- 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.
- 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.
- Eric Riedl. Largest and smallest minimal percolating sets in trees, The Electronic Journal of Combi- natorics, 19, 2010.
- Eric Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation, The Electronic Journal of Combinatorics, 17, 2010.
- W. H. Kautz, Unit distance error checking codes, in IRE Transaction on Electronic Computers, 7, 179–180, 1958.
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
- 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.
- 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.
- Eric Riedl. Largest and smallest minimal percolating sets in trees, The Electronic Journal of Combi- natorics, 19, 2010.
- Eric Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation, The Electronic Journal of Combinatorics, 17, 2010.
- W. H. Kautz, Unit distance error checking codes, in IRE Transaction on Electronic Computers, 7, 179–180, 1958.
Details
| Primary Language | English |
|---|---|
| Journal Section | Articles |
| Authors | |
| Publication Date | January 22, 2015 |
| Published in Issue | Year 2015 |