login
A357952
Maximum period of a totalistic cellular automaton on a connected graph with n nodes (counting the state of the updated node itself).
2
2, 2, 4, 6, 8, 18, 42, 112
OFFSET
1,1
COMMENTS
Each node can be in one of two states, ON or OFF. The automaton is totalistic, meaning that the state of a node in the next generation depends only on the number of ON-nodes among its neighbors and itself. 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 totalistic updating rules, and all initial states.
LINKS
The House of Graphs, Graph 21244.
Eric Weisstein's World of Mathematics, Spider Graph.
Eric Weisstein's World of Mathematics, Totalistic Cellular Automaton.
Wikipedia, Cellular automaton.
FORMULA
a(n) <= A357951(n).
EXAMPLE
Examples of optimal automata: (The updating rule is given as a set of integers, specifying how many of the neighbors of a node and the node itself must be ON for the node to be ON in the next generation.)
n = 1: Path graph; rule {0}; any initial state.
n = 2: Path graph; rule {0}; both nodes equal.
n = 3: Path graph; rule {1}; one of the end nodes ON.
n = 4: Path graph; rule {0,2}; one node ON.
n = 5: Spider graph with two legs of length 1 and one leg of length 2; rule {1}; one of the end nodes of the short legs ON.
n = 6: 2 X 3 grid with an additional diagonal edge; rule {0,1,3,5}; one degree 2 node (with neighbors of degree 2 and 3) ON.
n = 7: Graph 21244 in House of Graphs ('F@Unw' in graph6 format); rule {0,2,4,5,6}; one node of degree 3 and the node of degree 6 ON.
n = 8: Graph 'G?Dlvw' in graph6 format; rule {0,2,4}; one of the degree 4 nodes adjacent to the degree 6 node ON.
CROSSREFS
Sequence in context: A269298 A153964 A001010 * A091966 A231187 A055529
KEYWORD
nonn,more,hard
AUTHOR
STATUS
approved