Preprint 2009-24
Julio Aracena, Eric Fanchon, Marco Montalva, Mathilde Noual:
Combinatorics on update digraphs of discrete networks
Abstract:
Discrete networks have been used as models of gene regulation and other biological networks. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Aracena et al. (2009) was defined equivalence classes of deterministic update schedules according to the labeled digraph associated to the network (update digraph) and such that two schedules in the same class yield the same dynamical behavior. In this paper we study algorithmical and combinatorial aspects of update digraphs. We show a polinomial characterization of these digraphs, which enables to characterize the corresponding equivalence classes. We prove that the update digraphs are exactly the projections, on the respective subgraphs, of a complete update digraph. Finally, the exact number of complete update digraphs was determined, which provides upper and lower bounds on the number of equivalence classes.
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Eric FANCHON, Marco MONTALVA, Mathilde NOUAL: Combinatorics on update digraphs in Boolean networks. Discrete Applied Mathematics, vol. 159, 6, pp. 401–409, (2011).