Fixed points and maximal independent sets in AND-OR networks

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 2(n-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. (C) 2003 Elsevier B.V. All rights reserved.