A357951 Maximum period of an outer totalistic cellular automaton on a connected graph with n nodes.

2, 2, 4, 6, 16, 26, 66

Offset

1,1

Comments

Each node can be in one of two states, ON or OFF. The automaton is outer totalistic, meaning that the state of a node in the next generation depends only on the state of that node and the number of ON-nodes among its neighbors. Since there are finitely many states of the automaton, it will eventually enter a cycle. a(n) is the maximum of the length of that cycle, over all connected graphs with n nodes, all outer totalistic updating rules, and all initial states.

Links

Table of n, a(n) for n=1..7.

The House of Graphs, Graph 21096 (Beineke non-line graph G8).

Eric Weisstein's World of Mathematics, House Graph.

Eric Weisstein's World of Mathematics, Outer-Totalistic Cellular Automaton.

Wikipedia, Cellular automaton.

Example

Examples of optimal automata: (The updating rule is given as two sets of integers, where the first (second) set specifies how many neighbors must be ON for an OFF-node (ON-node) to turn (stay) ON.)
  n = 1: Path graph; rule {0}, {}; any initial state.
  n = 2: Path graph; rule {0,1}, {}; any initial state.
  n = 3: Path graph; rule {1}, {0,2}; one of the end nodes ON.
  n = 4: Path graph; rule {1}, {0,2}; one node ON.
  n = 5: House graph; rule {1}, {0,2}; one of the two "floor" nodes ON.
  n = 6: Beineke non-line graph G8 (2 X 3 grid with two parallell diagonals added); rule {0,2}, {1,3}; all nodes ON except one of degree 2.
  n = 7: Graph 'FBjng' in graph6 format; rule {0,1,3}, {2,4,5}; one node of degree 3 or 5 ON.

Crossrefs

Cf. A357952, A357953.

Sequence in context: A134041 A358366 A069925 * A227315 A080611 A171421

Adjacent sequences: A357948 A357949 A357950 * A357952 A357953 A357954

Keyword

nonn,more,hard

Author

Pontus von Brömssen, Oct 22 2022

Status

approved