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