OFFSET
1,2
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. 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 20561.
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 must be ON for the node to be ON in the next generation.)
n = 1: Path graph; rule {}; the node OFF.
n = 2: Path graph; rule {0}; both nodes equal.
n = 3: Path graph; rule {0}; all nodes OFF.
n = 4: Path graph; rule {1}; one of the end nodes ON.
n = 5: Complement of the union of a 2-node path and a 3-node path; rule {1,2}; the node of degree 2 ON.
n = 6: Divisor graph of {1,...,6} (there is an edge between i and j if i is a divisor of j or j is a divisor of i); rule {0,2}; nodes 1 and 2 ON.
n = 7: Graph 20561 in House of Graphs ('FJe~O' in graph6 format); rule {0,2}; one node of degree 3 ON.
n = 8: Graph 'G?CidW' in graph6 format; rule {0,2,4}; the node of degree 3 ON.
CROSSREFS
KEYWORD
nonn,more,hard
AUTHOR
Pontus von Brömssen, Oct 22 2022
STATUS
approved