cp's OEIS Frontend

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.

%I A350785 #8 Jan 27 2022 21:01:15
%S A350785 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,
%T A350785 4,118,799,3618,5603,975,0,0,4,194,2070,18996,102301,127692,9823,0,0,
%U A350785 4,312,4885,84043,1194264,6652289,3645810,134964,0
%N 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.
%C A350785 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.
%C A350785 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.
%e A350785 Triangle begins:
%e A350785   n\k| 1  2   3    4     5       6       7       8      9 10
%e A350785   ---+------------------------------------------------------
%e A350785    1 | 1
%e A350785    2 | 1  0
%e A350785    3 | 0  2   0
%e A350785    4 | 0  4   2    0
%e A350785    5 | 0  4  12    5     0
%e A350785    6 | 0  4  34   53    21       0
%e A350785    7 | 0  4  69  244   421     115       0
%e A350785    8 | 0  4 118  799  3618    5603     975       0
%e A350785    9 | 0  4 194 2070 18996  102301  127692    9823      0
%e A350785   10 | 0  4 312 4885 84043 1194264 6652289 3645810 134964  0
%Y A350785 Cf. A337663, A350764.
%Y A350785 Row sums: A001349.
%K A350785 nonn,tabl
%O A350785 1,5
%A A350785 _Pontus von Brömssen_, Jan 16 2022