### Abstract

Let G=(V,E) be a graph with an initial sign s(v)∈{±1} for every vertex v∈V. When a certex v becomes active, it resets its sign to s′(v) which is the sign of the majority of its neighbors (s′(v)=1 if there is a tie). G is in a stable state if, s′(v) for all v∈V. We show that for every graph G=(V,E) and every initial signs, there is a sequence v_{ 1}, v_{ 2}, ...,v_{ r} of vertices of G, in which no vertex appears more than once, such that if v_{ i} becomes active at time i, (1≤i≤r), then after these r steps G reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with weighted edges.

Original language | English (US) |
---|---|

Pages (from-to) | 305-310 |

Number of pages | 6 |

Journal | Graphs and Combinatorics |

Volume | 1 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1 1985 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Asynchronous threshold networks'. Together they form a unique fingerprint.

## Cite this

Alon, N. (1985). Asynchronous threshold networks.

*Graphs and Combinatorics*,*1*(1), 305-310. https://doi.org/10.1007/BF02582959