login
A370072
Triangle read by rows: T(n,k) is the number of unlabeled n-vertex graphs that are reachable in k (but no fewer) steps from the empty n-vertex graph, where a step consists of choosing a subset S of the vertices and replacing the subgraph induced by S by its complement, 0 <= k <= n-1.
3
1, 1, 1, 1, 2, 1, 1, 3, 6, 1, 1, 4, 14, 14, 1, 1, 5, 26, 73, 50, 1, 1, 6, 42, 226, 541, 227, 1, 1, 7, 63, 558, 3127, 6962, 1627, 1
OFFSET
1,5
COMMENTS
Equivalently, T(n,k) is the number of unlabeled n-vertex graphs that are the XOR sum of k (but no fewer) complete graphs, where the XOR sum of a set of graphs has edges between those pairs of vertices that are adjacent in an odd number of graphs in the set. (The set of vertices is initialized to [n], so the complete graphs in the sum are needed for the edges only.)
Any n-vertex graph G can be obtained from the empty graph in at most n-1 steps: the first step can be done so that all edges incident to the first vertex agree with G, the second step can be done so that all edges incident to the second vertex agree with G (without changing any edges incident to the first vertex), etc. After the (n-1)-st step, all edges agrees with G.
Apparently, the path graph is the unique n-vertex graph that requires n-1 steps.
EXAMPLE
Triangle begins:
1;
1, 1;
1, 2, 1;
1, 3, 6, 1;
1, 4, 14, 14, 1;
1, 5, 26, 73, 50, 1;
1, 6, 42, 226, 541, 227, 1;
1, 7, 63, 558, 3127, 6962, 1627, 1;
...
CROSSREFS
Cf. A000088 (row sums), A370073 (connected graphs), A370609 (labeled version).
Sequence in context: A111528 A363007 A144303 * A287024 A107702 A174480
KEYWORD
nonn,tabl,more
AUTHOR
STATUS
approved