Fixed points and maximal independent sets in AND–OR networks

AbstractWe 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