Maximal induced paths and minimal percolating sets in hypercubes
| Autor: | Anil M. Shende |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Induced path lcsh:Mathematics Percolating sets lcsh:QA1-939 Condensed Matter::Disordered Systems and Neural Networks Graph Vertex (geometry) Combinatorics Mathematics::Probability Condensed Matter::Statistical Mechanics Induced paths Discrete Mathematics and Combinatorics Hypercube Hypercubes Mathematics |
| Zdroj: | Journal of Algebra Combinatorics Discrete Structures and Applications, Vol 2, Iss 1, Pp 17-24 (2015) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|