[Cellular automaton state] network properties
The number of nodes and connections at step t > 1 are: rule 108: 8, 13; rule 128: 2t, 2t + 2; rule 132: 2t + 1, 3t + 3; rule 160: (t + 1)2, (t + 1)(t + 3); rule 184: 2t, 3t + 1. For rule 126 the first few cases are
{{1, 2}, {3, 5}, {13, 23}, {106, 196}, {2866, 5474}}
and for rule 110 they are
{{1,2}, {5, 9}, {20, 38}, {206, 403}, {1353, 2666}}
The maximum size of network that can possibly be generated after t steps of cellular automaton evolution is 2k2 r t - 1. For t = 1 the maximum of 15 (with 29 connections) is achieved for 16 out of the 256 possible elementary rules, including 22, 37, 73, 94, 104, 122, 146 and 164. For t = 2, rule 22 gives the largest network, with 280 nodes and 551 arcs. The k = 2, r = 2 totalistic rule with code 20 gives a network with 65535 nodes after just 1 step. Note that rules which yield maximal size networks are in a sense close to allowing all possible sequences. (The shortest excluded block for code 20 is of length 36.)