### Fixed points and maximal independent sets in AND-OR networks

### 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. © 2003 Elsevier B.V. All rights reserved.

### Más información

Título según WOS: | Fixed points and maximal independent sets in AND-OR networks |

Título según SCOPUS: | Fixed points and maximal independent sets in AND-OR networks |

Título de la Revista: | DISCRETE APPLIED MATHEMATICS |

Volumen: | 138 |

Número: | 3 |

Editorial: | Elsevier |

Fecha de publicación: | 2004 |

Página de inicio: | 277 |

Página final: | 288 |

Idioma: | English |

DOI: |
10.1016/S0166-218X(03)0046-1X |

Notas: | ISI, SCOPUS |