A350785 Triangle read by rows: T(n,k) is the number of (unlabeled) connected graphs with n nodes such that k is the maximum number that can be reached when the stepping stone puzzle of A337663 is played on the graph, 1 <= k <= n.

1, 1, 0, 0, 2, 0, 0, 4, 2, 0, 0, 4, 12, 5, 0, 0, 4, 34, 53, 21, 0, 0, 4, 69, 244, 421, 115, 0, 0, 4, 118, 799, 3618, 5603, 975, 0, 0, 4, 194, 2070, 18996, 102301, 127692, 9823, 0, 0, 4, 312, 4885, 84043, 1194264, 6652289, 3645810, 134964, 0

Offset: 1

Author

Pontus von Brömssen, Jan 16 2022

Keywords

• nonn
• tabl

Comments

The puzzle is as described in A337663, but the numbers are placed on the nodes of a graph. Initially, the number 1 is placed on some of the nodes. After that, the numbers 2, 3, ... are placed, in order, on unused nodes. When the number m is placed on a node, the sum of the numbers already placed on the neighbors of that node must equal m.

The maximum reachable number for a graph G is 2 if and only if G is a path, a cycle, a star, or a complete graph, with at least three nodes. As a result, T(n,2) = 4 for n >= 4. (For graphs with three nodes, the path and the star are isomorphic, and the cycle and the complete graph are isomorphic, so T(3,2) = 2.) Proof: It is easy to see that the maximum reachable number for paths, cycles, stars, and complete graphs is 2 if the graph has at least three nodes, and 1 if it has one or two nodes. Assume that G is a connected graph which is not a path, cycle, star, or a complete graph. We must show that the number 3 can be placed on one of its nodes. Let C be a maximum clique of G, and first assume that it has size at least three. Since G is not complete, there is a node u adjacent to some, but not all, nodes in C. Let x, y, and z be nodes in C such that u is adjacent to x but not to y. We can then put 1's on u and z, 2 on x, and 3 on y. Next, assume that the size of C is less than three, i.e., that G is triangle-free. Since G is not a path or a cycle, G has a node x of degree at least three. Since G is triangle-free, there are no edges between the neighbors of x. Since G is not a star, x has a neighbor y which is adjacent to another node z. We can then put 1's on z and two of the neighbors of x other than y, 2 on x, and 3 on y.

Examples

			Triangle begins:
  n\k| 1  2   3    4     5       6       7       8      9 10
  ---+------------------------------------------------------
   1 | 1
   2 | 1  0
   3 | 0  2   0
   4 | 0  4   2    0
   5 | 0  4  12    5     0
   6 | 0  4  34   53    21       0
   7 | 0  4  69  244   421     115       0
   8 | 0  4 118  799  3618    5603     975       0
   9 | 0  4 194 2070 18996  102301  127692    9823      0
  10 | 0  4 312 4885 84043 1194264 6652289 3645810 134964  0
		

Crossrefs

Cf. A337663, A350764.

Row sums: A001349.