# Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems

Abhijin Adiga, Chris J. Kuhlman, Henning S. Mortveit, Sichao Wu

► To cite this version:

Abhijin Adiga, Chris J. Kuhlman, Henning S. Mortveit, Sichao Wu. Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. pp.59-70, 10.1007/978-3-662-47221-7_5. hal-01442482

HAL Id: hal-01442482

https://inria.hal.science/hal-01442482

Submitted on 20 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems

Abhijin Adiga,<fnref n="1" /> Chris J. Kuhlman,<fnref n="1" /> Henning S. Mortveit,¹² and Sichao Wu<fnref n="1" />

**Abstract.** We study the attractor structure of standard block-sequential threshold dynamical systems. In a block-sequential update, the vertex set of the graph is partitioned into blocks, and the blocks are updated sequentially while the vertices within each block are updated in parallel. There are several notable previous results concerning the two extreme cases of block-sequential update: (i) sequential and (ii) parallel. While parallel threshold systems can have limit cycles of length at most two, sequential systems can have only fixed points. However, Goles and Montealegre [5] showed the existence of block-sequential threshold systems that have arbitrarily long limit cycles. Motivated by this result, we study how the underlying graph structure influences the limit cycle structure of block-sequential systems. We derive a sufficient condition on the graph structure so that the system has only fixed points as limit cycles. We also identify several well-known graph families that satisfy this condition.

**Keywords:** graph dynamical systems, generalized cellular automata, threshold functions, block decomposition

## 1 Introduction

In this paper, we study Boolean graph dynamical systems or automata networks induced by threshold functions. Such systems are a natural choice to model various biological and sociological phenomena (see [8,7,6,11] for example). We consider *standard Boolean threshold functions* where, each vertex $v$ is associated with a *threshold* $T_v$, and the vertex function of $v$ evaluates to 1 if and only if at least $T_v$ vertices in its closed neighborhood ($v$ and its distance-1 neighbors) are in state 1. These systems have been extensively studied [4,3,1]. Several generalizations of standard threshold functions have been considered in the past. For example in [10], *bi-threshold systems* were studied where the thresholds for the 0 to 1 and 1 to 0 transitions can be different. Multi-threshold systems with more than 2 possible vertex states were considered in [9,4]. In [14], systems with *dynamic thresholds* were considered where the vertex thresholds vary with time. Another popular variant of the standard threshold function are Hopfield networks, where only the open neighborhood is considered while evaluating the next state, i.e., the state of the vertex itself is ignored.

<footnote n="1">¹ Network Dynamics and Simulation Science Laboratory, VBI, Virginia Tech</footnote>

<footnote n="2">² Department of Mathematics, Virginia Tech</footnote>

<footnote>`{abhijin,ckuhlman,hmortvei,sichao}@vbi.vt.edu`</footnote>
Our focus is on the *limit set* or the *attractor structure* of these systems which captures their “long-term” behavior. The *update scheme*, i.e., the order in which the vertex functions are evaluated, influences the attractor structure and in general the phase space. Two update schemes (i) *synchronous* or parallel and (ii) *sequential* are well-studied. In the synchronous update scheme, every vertex function is applied simultaneously, while in a sequential update scheme, vertices are updated one by one according to a total order defined on the vertex set. A generalization of these schemes is the *block-sequential update*. Here, the vertices are partitioned into blocks, and vertices within the blocks are updated synchronously while the blocks themselves are updated sequentially. A more general sequential scheme is the *word update* which is a generalization of the sequential systems. Here, a vertex can be updated more than once in a single time step [12].

Two interesting questions which have been repeatedly addressed in the past are: given a graph dynamical system, (i) what is the maximum possible length of a limit cycle? (ii) what conditions lead to only fixed points as limit sets? There are some notable results in the case of standard threshold systems. Goles and Olivos [3] and Barrett et al. [1] independently, using different methods, showed that sequential threshold systems exhibit only fixed points as limit cycles. In [4,3], it was shown that for synchronous update there can be limit cycles of length at most two. Their result is applicable for the more general case of weighted threshold functions. Kuhlman et al. [10] considered these questions regarding bi-threshold systems. They showed that, while synchronous systems can have limit cycles of length at most two, sequential systems can have arbitrarily long limit cycles.

In this paper, we consider standard threshold systems with block-sequential update. Mortveit [13] showed that if the blocks are of size at most 3, then there will be only fixed points. The author also conjectured that the limit cycle length can be at most two for arbitrary block size. However, this was disproved recently by Goles and Montealegre [5]. Unlike the sequential or synchronous cases, these systems can have arbitrarily long limit cycles. In [4], the more general setting of weighted threshold functions was studied. They gave a sufficient condition for the system to have only fixed points. In this work, we examine standard threshold systems from a structural perspective. Our main objective was to identify conditions on the underlying graph structure which lead to only fixed points. Our main result is given below.

**Theorem 1.** Let $X$ be a simple graph with vertex set $V[X]$ and edge set $E[X]$. Let $\mathcal{B}$ be a block partition of $V[X]$. If every block $B \in \mathcal{B}$ satisfies Condition (1) below, then, any block-sequential standard threshold system induced by $\mathcal{B}$ for any update order on the blocks has only fixed points as limit sets. Also, the transient length is at most $\frac{|E[X]| + |V[X]| + 1}{2}$.

For any non-empty $B' \subseteq B$ and any assignment $y$ of vertex states for $B'$, $||B'|| - 2|\Lambda_{B'}(y)| - |B'| < 0$, where, $||B'||$ is the number of edges in the subgraph induced by $B'$ and $\Lambda_{B'}(y) = \{\{u, v\} \in E[X] \mid u, v \in B'$, and $y_u = y_v\}$. (1)
An interesting feature of Theorem 1 is that Condition (1) only applies to the individual blocks and is independent of the connections between the blocks. The proof uses the potential function argument introduced in [1]. We build on the framework provided by [13] and extend the results of that paper. We also show that simple graph classes such as trees and complete graphs satisfy Condition (1). In addition, we show that any graph which can be block-decomposed into subgraphs which satisfy Condition (1), also satisfies this condition.

We note that Condition (1) is not a necessary condition. Consider any graph with arbitrary block partition where each vertex has threshold 1. This is a progressive threshold system, i.e., a vertex will never transition from 1 to 0. Hence, it has only fixed points even though the blocks may not satisfy Condition (1).

The organization of the paper is as follows. We introduce the notation and basic definitions in the next section. In Section 3, we prove Theorem 1. In Section 4, we derive the block-decomposition result. In Section 5, we demonstrate some graph classes which satisfy Condition (1) before we conclude in Section 6.

## 2 Preliminaries

Let $X$ be a simple undirected graph on $n$ vertices with vertex set $V[X]$ and edge set $E[X]$. Let $\mathcal{B} = \{B_1, B_2, \dots, B_m\}$ be a block partition of $V[X]$. For $S \subseteq V[X]$, let $\deg_S(v)$ denote the number of neighbors of $v$ in the graph induced by $S$, and let $\deg(v)$ be its degree in $X$. $x_v$ denotes the vertex state of $v$. Since we are considering Boolean systems, $x_v \in \{0, 1\}$. Let $x = (x_1, x_2, \dots, x_n)$ be the system state. Let $n[v]$ denote the sorted sequence of the closed neighborhood of $v$, and let $x[v]$ denote the restriction of $x$ to $n[v]$.

Every vertex is assigned a threshold function $f_v : \{0, 1\}^{\deg(v)+1} \to \{0, 1\}$ defined as follows:

$$f_v(x[v]) = \begin{cases} 1, & \text{if } \sum_{w \in n[v]} x_w \ge T_v, \\ 0, & \text{otherwise,} \end{cases} \qquad (2)$$

where $T_v \in \mathbb{N}$ with $T_v \ge 1$ is the threshold of $v$. For a block $B$ and system state $x$, the map $F_B(x) : \{0, 1\}^n \to \{0, 1\}^n$ is given by

$$(F_B(x))_v = \begin{cases} f_v(x[v]), & \text{if } v \in B, \\ x_v, & \text{otherwise.} \end{cases} \qquad (3)$$

The block-sequential map $F : \{0, 1\}^n \to \{0, 1\}^n$ is defined as

$$F = F_{B_m} \circ F_{B_{m-1}} \circ \dots \circ F_{B_1}. \qquad (4)$$

The two special cases of the block-sequential update scheme are sequential and parallel update schemes. The sequential update corresponds to each vertex belonging to a distinct block, i.e., for $i = 1, \dots, n$, $|B_i| = 1$ and therefore, $m = n$. In parallel update, there is only one block, i.e., $m = 1$ and $B_1 = V[X]$.
# 3 Sufficient condition for fixed points

## 3.1 Potential function method

For $v \in V[X]$, let $T_0(v)$ denote the smallest number of vertices in $n[v]$ that must be in state 0 for $x_v$ to be mapped to zero. By the definition of threshold function in (2), we have $T_0(v) + T(v) = \deg(v) + 2$. With each vertex and edge, we associate a potential. The vertex potential for vertex $v$ and system state $x$ is

$$P(x, v) = \begin{cases} T(v), & x_v = 1, \\ T_0(v), & x_v = 0. \end{cases} \qquad (5)$$

The edge potential for edge $e = \{v, v'\}$ is

$$P(x, e) = \begin{cases} 1, & x_v \neq x_{v'}, \\ 0, & \text{otherwise.} \end{cases} \qquad (6)$$

The system potential function $P: \{0, 1\}^n \to \mathbb{N}$ for state $x$ is defined as

$$P(x) = \sum_{v \in V[X]} P(x, v) + \sum_{e \in E[X]} P(x, e). \qquad (7)$$

For sequential threshold systems, Barrett et al. [1] showed that for any $x' = F(x)$ where $x \neq x'$, $P(x') < P(x)$. Since $P(x) \ge 0$ for all $x$, it follows that the limit set is comprised of only fixed points. They also showed that the transient length is at most $(|E[X]| + |V[X]| + 1)/2$ as a consequence of this result. The same argument was applied by Mortveit [13] for block-sequential systems with blocks of size at most three.

## 3.2 Proof of Theorem 1

Suppose the system transitions from state $x$ to $x'$ when a block $B$ is updated, i.e. $x' = F_B(x)$. Let $\Delta P = P(x') - P(x)$. Let $P_v(x) = P(x, v) + \sum_{e \in E_v[X]} P(x, e)$, where $E_v[X]$ is the set of edges incident with $v$. Let $\Delta P_v = P_v(x') - P_v(x)$ denote the change in potential at vertex $v$. Note that since only block $B$ is updated, $\forall v \notin B$, $x_v = x'_v$. Let $B(x, x') \subseteq B$ denote the set of vertices such that $x_v \neq x'_v$. We use the following result from Mortveit [13].

**Lemma 2 (Mortveit [13]).** $\Delta P = \sum_{v \in B(x, x')} \Delta P_v$.

The lemma below gives an upper bound for $\Delta P_v$.

**Lemma 3.** For any $v \in B(x, x')$, let $\gamma_v$ denote the number of neighbors of $v$ in $B(x, x')$ which have the same state as $v$ in $x$ (and therefore, in $x'$). Applying $F_B$, $\Delta P_v \le \deg_{B(x, x')}(v) - 2\gamma_v - 2$.

*Proof.* In [13], $\Delta P_v$ is bounded as a function of $\deg_B(v)$ and the number of vertices in state 1 in $x$. We apply the same approach here, but obtain a more compact result. Let $n_1(x, v)$ and $n_0(x, v)$ denote the number of neighbors of $v$ in state 1 and 0 respectively. There are two possible cases: $v$ transitions either from 0 to 1 or 1 to 0. We consider these cases separately.
**Transition 0 → 1.** Note that $n_1(x) \ge T(v)$. We recall that $T(v) + T_0(v) = \deg(v) + 2$. Also, since only vertices in $B(x, x')$ change state,

$$ 
\begin{aligned}
n_0(x', v) &= n_0(x, v) + (\text{number of neighbors of } v \text{ in } B(x, x') \text{ in state 1 in } x) \\
&\quad - (\text{number of neighbors of } v \text{ in } B(x, x') \text{ in state 0 in } x) \\
&= n_0(x, v) + (\deg_{B(x,x')}(v) - \gamma_v) - \gamma_v \\
&= \deg(v) - n_1(x, v) + \deg_{B(x,x')}(v) - 2\gamma_v.
\end{aligned} 
\tag{8} $$

Now we compute $\Delta P_v$.

$$ 
\begin{aligned}
\Delta P_v &= (T(v) + n_0(x', v)) - (T_0(v) + n_1(x, v)) \\
&= T(v) + (\deg(v) - n_1(x, v) + \deg_{B(x,x')}(v) - 2\gamma_v) \\
&\quad - (\deg(v) + 2 - T(v) + n_1(x, v)) \\
&= 2(T(v) - n_1(x, v)) + (\deg_{B(x,x')}(v) - 2\gamma_v - 2) \\
&\le \deg_{B(x,x')}(v) - 2\gamma_v - 2.
\end{aligned} 
$$

**Transition 1 → 0.** In this case, we have $n_1(x) \le T(v) - 2$. Following a similar approach as in (8), it can be shown that $n_1(x', v) = n_1(x, v) + \deg_{B(x,x')}(v) - 2\gamma_v$.

$$ 
\begin{aligned}
\Delta P_v &= (T_0(v) + n_1(x', v)) - (T(v) + n_0(x, v)) \\
&= (\deg(v) + 2 - T(v)) + (n_1(x, v) + \deg_{B(x,x')}(v) - 2\gamma_v) \\
&\quad - T(v) - (\deg(v) - n_1(x, v)) \\
&= 2(n_1(x, v) - T(v)) + 2 + (\deg_{B(x,x')}(v) - 2\gamma_v) \\
&\le \deg_{B(x,x')}(v) - 2\gamma_v - 2.
\end{aligned} 
$$

□

For a set of vertices $S \subseteq V[X]$, let $\|S\|$ denote the number of edges in $X[S]$, the subgraph induced by $S$. For a state vector $x$, let $\Lambda_S(x) = \{(u, v) | u, v \in S, x_u = x_v \text{ and } \{u, v\} \in E[X]\}$, i.e., the set of all pairs of adjacent vertices in $S$ which have the same state.

**Lemma 4.** $\Delta P = P(x') - P(x) \le 2(\|B(x, x')\| - 2|\Lambda_{B(x,x')}(x)| - |B(x, x')|)$.

*Proof.* From Lemma 2, $P(x') - P(x) = \sum_{v \in B(x,x')} \Delta P_v$. Applying Lemma 3, $P(x') - P(x) \le 2(\|B(x, x')\| - \sum_{v \in B(x,x')} \gamma_v - |B(x, x')|)$. Note that for each $(u, v) \in \Lambda_{B(x,x')}(x)$, $v$ contributes 1 to $\gamma_u$ and $u$ contributes 1 to $\gamma_v$. Moreover, if $(u, v) \notin \Lambda_{B(x,x')}(x)$, then, it does not contribute to the sum. Therefore, $\sum_{v \in B(x,x')} \gamma_v = \sum_{(u,v) \in \Lambda_{B(x,x')}(x)} 2 = 2|\Lambda_{B(x,x')}(x)|$. Hence proved. □

**Lemma 5.** Let block B satisfy Condition (1). Then, for any $x' = F_B(x)$ such that $x' \ne x$, $P(x') < P(x)$.
*Proof.* From Lemma 4, $\Delta P \le 2(\|B(x, x')\| - 2|\Lambda_{B(x,x')}(x)| - |B(x, x')|)$. Let $B' = B(x, x')$ and $y$ be the state vector restricted to $B(x, x')$. Since $x' \ne x$, $B'$ is not empty. Therefore, by Condition (1), $\|B'\| - 2|\Lambda_{B'}(y)| - |B'| < 0$. $\square$

From Lemma 5, we note that if every block satisfies Condition (1), then, whenever a block is updated and some vertices change states, the system potential decreases. Since the potential cannot be negative by definition, it follows that there can be only fixed points as limit sets. Hence, we have proved Theorem 1.

# 4 Block decomposition

In the graph theory literature, a *block* is a maximal connected subgraph without a cut vertex [2]. Every block can either be a maximal 2-connected subgraph, an edge, or an isolated vertex. Since the term “block” has already been used to mean something else in this paper, we will henceforth refer to maximal connected subgraphs as *subblocks*. Every graph can be decomposed into subblocks. Since they satisfy maximality, any two subblocks overlap in at most one vertex, which, if it exists, is a cut vertex of the graph. This is illustrated with an example in Figure 1(a). Let $C$ be the set of cut vertices and $S$ be the set of subblocks. The *block graph* is the bipartite graph on the vertex set $C \cup S$ where for $c \in C$ and $S \in S$, $\{c, S\}$ is an edge if and only if $c \in S$. It can be easily shown that the block graph is a tree. See Figure 1(b) for the block graph of the example.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** An example of (a) a block decomposition and (b) the corresponding block graph.</figcaption></figure>

**Theorem 6.** Let block B be such that all of its subblocks satisfy Condition (1). Then, B satisfies Condition (1) too.
**Proof.** Let {$S^1, \dots, S^k$} be the vertex partition of $B$ where each $S^i$ induces a subblock of $B$. From the block graph representation, it is easy to see that there exists an ordering of the subblocks such that every subblock has at most one cut vertex in common with its previous subblocks. We will assume that the current ordering satisfies this property, i.e.,

$$ |(\cup_{j<i} S^j) \cap S^i| = 1, \forall i = 1, \dots, k. \qquad (9) $$

Let $D \subseteq B$ and $D^i = D \cap S^i$. From (9), we have $|D| \ge |D^1| + \sum_{i=2}^k (|D^i| - 1)$. For a subset of vertices $S$, let $E_S$ denote the edge set of the graph induced by $S$. We observe that the edge sets $E_{S^i}$ partition $E_B$. This implies that $E_{D^i}$ are mutually disjoint. Since $\Lambda_{D^i}(x) \subseteq E_{D^i}$, they are mutually disjoint too. we have

$$ \begin{aligned} \|D\| - 2\Lambda_D(x) - |D| &\le \sum_{i=1}^k (\|D^i\| - 2\Lambda_{D^i}(x)) - (|D^1| + \sum_{i=2}^k (|D^i| - 1)) \\ &= (\|D^1\| - 2\Lambda_{D^1}(x) - |D^1|) + \sum_{i=2}^k (\|D^i\| - 2\Lambda_{D^i}(x) - |D^i| + 1). \end{aligned} $$

Since all the subblocks satisfy the Condition (1), the first term in the above expression is negative while the second term is at most 0. Hence, $\|D\| - 2\Lambda_D(x) - |D| < 0$. $\square$

# 5 Simple graph classes which satisfy Condition (1)

We will show that some graph classes such as trees, odd cycles, and complete graphs satisfy Condition (1). Even though these are very simple graphs, to the best of our knowledge, these results have not been obtained before using any other method. Throughout this section, $B$ corresponds to a block in $X$ and $B' \subseteq B$.

**Proposition 7.** If $B$ induces a tree in $X$, then, it satisfies Condition (1).

**Proof.** Suppose $B' \subseteq B$. If the graph induced by $B'$ is connected, then it still corresponds to a tree. If not, then, each connected component (which is also a tree) in the graph can be considered independent of the rest of the block. In that case, effectively we are working with a smaller tree. Hence, without loss of generality, we will assume that $B'$ is connected (and can be the same as $B$). Since $\|B'\| = |B'| - 1$, it implies that $B$ satisfies Condition (1). $\square$

Alternatively, we could have used Theorem 6 to prove the above proposition.

**Proposition 8.** If $B$ induces an odd cycle in $X$, then, it satisfies Condition (1).

**Proof.** If $B' \subseteq B$, then it corresponds to a collection of disconnected paths. Then, we can apply Proposition 7 to show that $B'$ satisfies the condition. Therefore, we will assume that $B' = B$. We first note that $\|B\| = |B|$. Since the cycle is odd, there exists by the pigeonhole principle, at least one pair of vertices in $\Lambda_{B'}(y)$ for any state vector $y$. Hence, for all $B' \subseteq B$, $\|B\| - 2\Lambda_B(y) - |B| < 0$. $\square$
**Proposition 9.** If B induces a clique in X, then, it satisfies Condition (1).

*Proof.* If $B' \subset B$, then it still induces a clique. Hence, we will assume that $B' = B$. Let $y$ be the state vector restricted to $B$. Let $n_0$ denote the number of vertices of $B$ in state 0 and let $n = |B|$. Since, $B$ is a clique, $|\Lambda_B(x)| = \binom{n_0}{2} + \binom{n-n_0}{2}$, which attains a minimum value of $\frac{1}{2}[(\lfloor \frac{n}{2} \rfloor)(\lfloor \frac{n}{2} \rfloor - 1) + \lfloor \frac{n}{2} \rfloor(\lfloor \frac{n}{2} \rfloor - 1)]$ at $n_0 = \lfloor \frac{n}{2} \rfloor$. Therefore,

$$ \begin{aligned} \|B\| - 2|\Lambda_B(x)| - |B| &= \binom{n}{2} - 2|\Lambda_B(x)| - n \\ &< \lfloor \frac{n}{2} \rfloor - n = - \lfloor \frac{n}{2} \rfloor. \end{aligned} \quad \square $$

The next result concerns systems with block size at most 4. This is an extension of the result by Mortveit [13].

**Proposition 10.** Any block B of size 4 other than the 4-cycle, satisfies Condition (1).

*Proof.* If $B' \subset B$, then it corresponds to a block of size 3 or less, for which the result follows from [13]. Hence, we will assume that $B' = B$. If $B$ is a tree or clique, then, by Propositions 7 and 9, the statement is true. The remaining possibilities excluding the 4-cycle are isomorphic to one of the graphs illustrated in Figure 2. We consider them one by one and in each case show that $\|B\| - 2|\Lambda_B(x)| - |B| < 0$ and the rest follows from Lemma 4.

**Graph (a)** In this case, $|B| = \|B\| = 4$ and since $\{2, 3, 4\}$ induces an odd cycle, it implies that $\Lambda_{B(x,x')}(x)$ is not empty and therefore $|\Lambda_{B(x,x')}(x)| \ge 1$.

**Graph (b)** Here, $\|B\| = 5$ and again, since $\{2, 3, 4\}$ (or $\{1, 3, 4\}$) induces an odd cycle, $|\Lambda_{B(x,x')}(x)| \ge 1$.

**Graph (c)** The argument is similar to the previous case. □

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Possible connected graphs (up to isomorphism) of size 4 excluding trees and 4-cycle.</figcaption></figure>
**Remark 11.** Note that one can configure an example corresponding to a 4-cycle ($C_4$) for which not satisfies Condition (1) (See Figure 3(a)). Moreover, this configuration corresponds to a limit cycle of length 2. So, a natural question to ask is whether graphs which do not have a $C_4$ as a vertex-induced subgraph not satisfies Condition (1) for all $x$. Unfortunately, the answer is no. Figure 3(b) is an example where an induced-$C_4$-free graph has a limit cycle of length two.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Configurations which lead to limit cycles of length two: if the black vertices are in state 0, then the white are in 1, and vice versa. (a) Block $C_4$ where all vertices have threshold 2 and (b) an induced-$C_4$-free graph with the black vertices having threshold 2 and white vertices 3.</figcaption></figure>

**Proposition 12.** If $B$ is a wheel graph with odd cycle, then, it satisfies Condition (1).

*Proof.* A wheel graph is formed by connecting a single vertex to all vertices of a cycle. see Figure 4 (a) as an illustration. Let $B' \subseteq B$ and $y$ be the state vector restricted to $B'$. There are three cases that need to be considered.

(a) $B'$ does not contain the center vertex. In this case, $B'$ induces either an odd cycle or a collection of paths. Then, from Propositions 7 and 8, $\|B'\| - 2|\Lambda_{B'}(y)| - |B'| < 0$.

(b) $B' \subset B$ and contains the center vertex. In this case, the central vertex corresponds to a cut vertex (see Figure 4 (b)). Therefore, block decomposition of $B'$ yields subblocks, all of which have the following structure: a path graph where each vertex is connected to a central vertex. Let $B''$ be such a subblock (illustrated in Figure 4 (b)). We only need to show that $\|B''\| - 2\Lambda_{B''}(y) - |B''| < 0$. The rest follows from Theorem 6. Let $n = |B''|$. We have $\|B''\| = 2n - 3$.

Without loss of generality, we will assume that the state of the center vertex is 0. Let $Q$ denote the remaining set of vertices and of these, let $k$ be in state 0. It is clear that the rest $n - 1 - k$ vertices are in state 1. We have

$$|\Lambda_{B''}(y)| = k + |\Lambda_Q(y)|. \qquad (10)$$
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** (a) An exemplary wheel graph. (b) Induced sub-graph $B'$ of a wheel graph by removing multiple vertices from the cycle</figcaption></figure>

Now we claim that

$$|\Lambda_{B''}(y)| \geq \frac{n-2}{2}. \qquad (11)$$

If $k \geq \frac{n-2}{2}$, (11) trivially holds. Thus, we will assume that $k < \frac{n-2}{2}$. Note that each edge on $Q$ contributes 1 to $|\Lambda_Q(y)|$ if and only if the two vertices associated with the edge are in the same state. Therefore, $|\Lambda_Q(y)|$ will achieve its minimum value when all vertices in state 0 have their neighbors in state 1. And since $k < \frac{n-2}{2}$, it is guaranteed that such a configuration exists. In this case, $n-2-2k$ edges will contribute to $|\Lambda_Q(y)|$, i.e. we have, $|\Lambda_Q(y)| \geq n-2-2k$. This yields, $|\Lambda_{B''}(y)| = k + |\Lambda_Q(y)| \geq n-2-k > \frac{n-2}{2}$. Hence, (11) holds, which in turn implies that

$$\|B''\| - 2|\Lambda_{B''}(y)| - |B''| \leq 2n - 3 - 2 \cdot \frac{n-2}{2} - n \leq -1.$$

Hence, proved.

(c) $B' = B$, i.e. we consider the whole wheel graph. In this case, $|B| = n$ and $\|B\| = 2n-2$. Now, we will show that $\|B\| - 2|\Lambda_B(y)| - |B| < 0$. The argument is similar to the previous case. Let $Q$ denote the set of vertices in the cycle. Now, we will claim that

$$|\Lambda_B(y)| \geq \frac{n-1}{2}. \qquad (12)$$

Since $|\Lambda_B(y)| = k + |\Lambda_Q(y)|$, if $k \geq \frac{n-1}{2}$, the above inequality holds. We can thus assume $k < \frac{n-1}{2}$. There are $n-1$ edges on the cycle. Using the same arguments as
in the previous case, at most $2k$ edges do not contribute to the value of $|\Lambda_Q(y)|$, which means $|\Lambda_Q(y)| \ge n - 1 - 2k$. It follows that

$$|\Lambda_B(y)| = k + |\Lambda_Q(y)| \ge n - 1 - k > \frac{n-1}{2}.$$

Hence, (12) holds. We have,

$$\|B\| - 2|\Lambda_B(y)| - |B| \le 2n - 2 - 2 \cdot \frac{n-1}{2} - n \le -1.$$

Hence, proved. □

<figure><img src="image_6.png" /></figure>

*Remark 13.* Note that there exists a wheel graph with an even cycle corresponding to a limit cycle of length 2, see Figure 5. In this example, suppose the threshold value of the central vertex is 3 and all other vertices have threshold value 2. Then, one can verify that the central vertex will remain 0 and the other vertices will change states alternatively in pairs, i.e. this configuration leads to a length 2 limit cycle.

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Configuration over a wheel graph with an even cycle which leads to limit cycle of length 2. Black vertices are in state 0 and white are in state 1. The threshold value for the central vertex is 3, and 2 for other vertices.</figcaption></figure>

# 6 Conclusion

In this paper, we studied the limit cycle structure of standard threshold dynamical systems with block-sequential update. We identified a sufficient condition for the system to have only fixed points as limit sets. There are several possibilities to consider for the future. Even though the condition depends only on the blocks and not the graph as a whole, it seems to be restrictive. One direction to explore is to find more general conditions which take into account edges between the blocks too. Another direction would be to study bi-threshold block-sequential systems.
References

1. Barrett, C.L., Hunt, H.B., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of reachability problems for finite discrete dynamical systems. Journal of Computer and System Sciences 72(8), 1317–1345 (2006)

2. Diestel, R.: Graph Theory. Springer, 2 edn. (2000)

3. Goles, E., Olivos, J.: Comportement périodique des fonctions à seuil binaires et applications. Discrete Applied Mathematics 3(2), 93–105 (1981)

4. Goles, E., Martínez, S.: Neural and automata networks. Kluwer (1990)

5. Goles, E., Montealegre, P.: Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science 559(0), 3–19 (2014), http://www.sciencedirect.com/science/article/pii/S0304397514006756, non-uniform Cellular Automata

6. Granovetter, M.: Threshold models of collective behavior. American journal of sociology pp. 1420–1443 (1978)

7. Karaoz, U., Murali, T., Letovsky, S., Zheng, Y., Ding, C., Cantor, C.R., Kasif, S.: Whole-genome annotation by using evidence integration in functional-linkage networks. Proceedings of the National Academy of Sciences of the United States of America 101(9), 2888–2893 (2004)

8. Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of theoretical biology 22(3), 437–467 (1969)

9. Kuhlman, C.J., Mortveit, H.S.: Limit sets of generalized, multi-threshold networks. accepted in Journal of Cellular Automata (2015)

10. Kuhlman, C.J., Mortveit, H.S., Murrugarra, D., Kumar, V.S.A.: Bifurcations in boolean networks. Automata 2011 pp. 29–46 (2011)

11. Macy, M.W.: Chains of cooperation: Threshold effects in collective action. American Sociological Review pp. 730–747 (1991)

12. Mortveit, H., Reidys, C.: An introduction to sequential dynamical systems. Springer Science & Business Media (2007)

13. Mortveit, H.S.: Limit cycle structure for block-sequential threshold systems. In: Cellular Automata, pp. 672–678. Springer (2012)

14. Wu, S., Adiga, A., Mortveit, H.S.: Limit cycle structure for dynamic bi-threshold systems. Theoretical Computer Science (2014), http://www.sciencedirect.com/science/article/pii/S0304397514005088