Fixed points and maximal independent sets in AND-OR networks

Julio Aracena, Jacques Demongeot, Eric Goles

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

We study the maximum number of fixed points of boolean networks with local update function AND-OR. We prove that this number for networks with connected digraph is 2(n-1)/2 for n odd and 2(n-2)/2+1 for n even if the digraph has not loops; and 2n-1+1 otherwise, where n is the number of nodes of the digraph. We also exhibit some networks reaching these bounds. To obtain these results we construct a bijection between the maximal independent sets of the digraph and the fixed points of the network belonging to a particular family of AND-OR networks.

Original languageEnglish
Pages (from-to)277-288
Number of pages12
JournalDiscrete Applied Mathematics
Volume138
Issue number3
DOIs
StatePublished - 15 Apr 2004
Externally publishedYes

Keywords

  • AND-OR network
  • Bipartite graph
  • Digraph
  • Fixed point
  • Maximal independent set

Fingerprint

Dive into the research topics of 'Fixed points and maximal independent sets in AND-OR networks'. Together they form a unique fingerprint.

Cite this