On the Number of Control Nodes in Boolean Networks With Degree Constraints

In this study, we analyze the minimum control node set problem for Boolean networks (BNs) with degree constraints. Our major contribution is the derivation of nontrivial lower and upper bounds on the size of the minimum control node set through combinatorial analysis of four types of BNs (i.e., $k$ - $k$ -XOR-BNs, simple $k$ - $k$ -AND-BNs, $k$ - $k$ -AND-BNs with negation, and $k$ - $k$ -NC-BNs, where the indegree and outdegree of each node are both $k$ , and the $k$ - $k$ -AND-BN with negation is an extension of the simple $k$ - $k$ -AND-BN that considers the occurrence of negation and NC means nested canalyzing). More specifically, four bounds for the size of the minimum control node set: general lower bound, best case upper bound, worst-case lower bound, and general upper bound are analyzed. By dividing nodes into three disjoint sets, extending the time to reach the target state, and utilizing necessary conditions for controllability, these bounds are obtained. Further, meaningful results and phenomena are discovered. Notably, all of the above results involving the AND function also apply to the OR function.