Fixed points in conjunctive networks and maximal independent sets in graph contractions
Preprint
Abstract
Given a graph $G$, viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with $G$ as interaction graph. We prove that if $G$ has no induced $C_4$, then this quantity equals both the number of maximal independent sets in $G$ and the maximum number of maximal independent sets among all the graphs obtained from $G$ by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if $G$ has a unique induced $C_4$.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- From kernels in directed graphs to fixed points and negative cycles in Boolean networksDiscrete Applied Mathematics, 2013
- The Dynamics of Conjunctive and Disjunctive Boolean Network ModelsBulletin of Mathematical Biology, 2010
- Graphic requirements for multistability and attractive cycles in a Boolean dynamical frameworkAdvances in Applied Mathematics, 2008
- Maximum Number of Fixed Points in Regulatory Boolean NetworksBulletin of Mathematical Biology, 2008
- Pattern Formation by Lateral Inhibition with Feedback: a Mathematical Model of Delta-Notch Intercellular SignallingJournal of Theoretical Biology, 1996
- Packing directed circuitsCombinatorica, 1996
- On generating all maximal independent setsInformation Processing Letters, 1988
- Iterative behaviour of generalized majority functionsMathematical Social Sciences, 1983
- On periodical behaviour in societies with symmetric influencesCombinatorica, 1983
- Boolean formalization of genetic control circuitsJournal of Theoretical Biology, 1973