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
KEYWORD
nonn,more,hard
AUTHOR
Pontus von Brömssen, Oct 22 2022
STATUS
approved