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!)
A357951 Maximum period of an outer totalistic cellular automaton on a connected graph with n nodes. 2
2, 2, 4, 6, 16, 26, 66 (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 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
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
Sequence in context: A134041 A358366 A069925 * A227315 A080611 A171421
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 May 21 22:16 EDT 2024. Contains 372741 sequences. (Running on oeis4.)