BibTex RIS Kaynak Göster

Maximal induced paths and minimal percolating sets in hypercubes

Yıl 2015, Cilt: 2 Sayı: 1, 17 - 24, 22.01.2015
https://doi.org/10.13069/jacodesmath.15518

Öz

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.

Kaynakça

  • 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.

Maximal induced paths and minimal percolating sets in hypercubes

Yıl 2015, Cilt: 2 Sayı: 1, 17 - 24, 22.01.2015
https://doi.org/10.13069/jacodesmath.15518

Öz

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.

Kaynakça

  • 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.
Toplam 5 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Bölüm Makaleler
Yazarlar

Anil M. Shende Bu kişi benim

Yayımlanma Tarihi 22 Ocak 2015
Yayımlandığı Sayı Yıl 2015 Cilt: 2 Sayı: 1

Kaynak Göster

APA Shende, A. M. (2015). Maximal induced paths and minimal percolating sets in hypercubes. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(1), 17-24. https://doi.org/10.13069/jacodesmath.15518
AMA Shende AM. Maximal induced paths and minimal percolating sets in hypercubes. Journal of Algebra Combinatorics Discrete Structures and Applications. Mart 2015;2(1):17-24. doi:10.13069/jacodesmath.15518
Chicago Shende, Anil M. “Maximal Induced Paths and Minimal Percolating Sets in Hypercubes”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, sy. 1 (Mart 2015): 17-24. https://doi.org/10.13069/jacodesmath.15518.
EndNote Shende AM (01 Mart 2015) Maximal induced paths and minimal percolating sets in hypercubes. Journal of Algebra Combinatorics Discrete Structures and Applications 2 1 17–24.
IEEE A. M. Shende, “Maximal induced paths and minimal percolating sets in hypercubes”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 1, ss. 17–24, 2015, doi: 10.13069/jacodesmath.15518.
ISNAD Shende, Anil M. “Maximal Induced Paths and Minimal Percolating Sets in Hypercubes”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/1 (Mart 2015), 17-24. https://doi.org/10.13069/jacodesmath.15518.
JAMA Shende AM. Maximal induced paths and minimal percolating sets in hypercubes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:17–24.
MLA Shende, Anil M. “Maximal Induced Paths and Minimal Percolating Sets in Hypercubes”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 1, 2015, ss. 17-24, doi:10.13069/jacodesmath.15518.
Vancouver Shende AM. Maximal induced paths and minimal percolating sets in hypercubes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(1):17-24.