×

Maximum number of fixed points in AND-OR-NOT networks. (English) Zbl 1311.68100

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aracena, J., On the number of fixed points in regulatory boolean networks, Bull. Math. Biol., 70, 1398-1409 (2008) · Zbl 1144.92323
[2] Aracena, J.; Demongeot, J.; Goles, E., Fixed points and maximal independent sets in AND-OR-networks, Discrete Appl. Math., 138, 277-288 (2004) · Zbl 1076.68047
[3] Cutler, J.; Radcliffe, A. J., Extremal problems for independent set enumeration, Electron. J. Comb., 18, 1 (2011), #P169 · Zbl 1229.05138
[4] Dunne, P., The Complexity of Boolean Networks (1988), Academic Press: Academic Press CA · Zbl 0672.68012
[5] Füredi, Z., The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 463-470 (1987) · Zbl 0647.05032
[6] Galvin, D., Two problems on independent sets in graphs, Discrete Math., 311, 2105-2112 (2011) · Zbl 1228.05228
[7] Goles, E.; Hernández, G., Dynamical behavior of Kauffman networks with AND-OR gates, J. Biol. Syst., 8, 151-175 (2000)
[9] Griggs, J. R.; Grinstead, C. M.; Guichard, D. R., The number of maximal independent sets in a connected graph, Discrete Math., 68, 211-220 (1988) · Zbl 0652.05027
[10] Hua, H., A sharp upper bound for the number of stable sets in graphs with given number of cut edges, Appl. Math. Lett., 22, 1380-1385 (2009) · Zbl 1173.05333
[11] Hujter, M.; Tuza, Z., The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math., 6, 284-288 (1993) · Zbl 0779.05025
[12] Kahn, J., An entropy approach to the hard-core model on bipartite graphs, Comb. Probab. Comput., 10, 219-237 (2001) · Zbl 0985.60088
[13] Kauffman, S. A., Metabolic Stability and Epigenesis in Randomly Constructed Genetics nets, J. Theor. Biol., 22, 437-467 (1969)
[14] Kauffman, S. A., The Origins of Order, Self-Organization and Selection in Evolution (1993), Oxford University Press
[15] Liu, J., Maximal independent sets in bipartite graphs, J. Graph Theory, 17, 495-507 (1993) · Zbl 0783.05063
[16] Melkman, A.; Tamura, T.; Akutsu, T., Determining a singleton attractor of an AND/OR Boolean network in \(O(1.587^n)\) time, Inf. Process. Lett., 110, 565-569 (2010) · Zbl 1234.68156
[17] Meir, A.; Moon, J. W., On maximal independent sets of nodes in trees, J. Graph Theory, 12, 265-283 (1988) · Zbl 0655.05039
[18] Moon, J. W.; Moser, L., On cliques in graphs, Isr. J. Math., 3, 23-28 (1965) · Zbl 0144.23205
[19] Prodinger, H.; Tichy, R., Fibonacci numbers of graphs, Fibonacci Q., 20, 16-21 (1982) · Zbl 0475.05046
[20] Remy, E.; Ruet, P.; Thieffry, D., Graphic requirements for multistability and attractive cycles in a boolean dynamical framework, Adv. Appl. Math., 41, 335-350 (2008) · Zbl 1169.05333
[21] Robert, F., Discrete Iterations: A Metric Study, Ser. Comput. Math., vol. 6 (1986), Springer
[22] Thomas, R., Boolean formalization of genetic control circuits, J. Theor. Biol., 42, 563-585 (1973)
[23] Thomas, R.; d’Ari, R., Biological Feedback (1990), CRC Press · Zbl 0743.92003
[24] Tocci, R. J.; Widmer, R. S., Digital Systems: Principles and Applications (2001), Prentice Hall: Prentice Hall NJ
[25] Veliz-Cuba, A.; Laubenbacher, R., On the computation of fixed points in Boolean networks, J. Appl. Math. Comput., 39, 145-153 (2012) · Zbl 1381.94145
[26] Zhao, Y., The number of independent sets in a regular graph, Comb. Probab. Comput., 19, 315-320 (2010) · Zbl 1215.05140
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.