|
| |
|
|
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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
