Maximum number of fixed points in AND–OR–NOT networks

• We determine the maximum number of fixed points (MNFP) in AND–OR–NOT-networks.
• MNFP differs strongly when loops are allowed or not.
• MNFP is bounded above by the maximum number of independent sets of a graph.
• We also characterize the AND–OR–NOT-networks reaching these bounds.

We are interested in the number of fixed points in AND–OR–NOT networks, i.e. Boolean networks in which the update function of each component is either a conjunction or a disjunction of positive or negative literals. As the main result, we prove that the maximum number of fixed points in a loop-less connected AND–OR–NOT network with n components is at most the maximum number of maximal independent sets in a loop-less connected graph with n vertices, a quantity already known.