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.

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.

Links

Table of n, a(n) for n=1..36.

Pontus von Brömssen, Illustration of row n = 4.

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

Adjacent sequences: A370069 A370070 A370071 * A370073 A370074 A370075

Keyword

nonn,tabl,more

Author

Pontus von Brömssen, Feb 10 2024

Status

approved