The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 16:55 EDT 2024. Contains 373410 sequences. (Running on oeis4.)