|
| |
|
|
A331693
|
|
Number of Tom graphs with n vertices.
|
|
4
|
|
|
|
1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 328, 705, 1576, 3551, 8179, 18980, 44559, 105111, 249426, 593484, 1416269, 3384581, 8099819, 19398194, 46487665, 111447044, 267260387, 641022947, 1537706522, 3688974818, 8850411933, 21234093757, 50946316856, 122234742311
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
This sequence is from a Project Euler problem called "Tom and Jerry". A cat named Tom and a mouse named Jerry play a game on a graph G. Each vertex of G is a mousehole. Jerry starts in one of the vertices. Every day, Tom tries to catch Jerry in one of the holes. If there is a vertex adjacent to Jerry's hole, then Jerry moves to one of the adjacent holes. A Tom graph is a graph on which Tom can always catch Jerry by following a sequence of holes.
All Tom graphs are loop-free graphs, but not all loop-free graphs are Tom graphs. The smallest loop-free graph that is not a Tom graph has 10 vertices:
1
|
2
|
3
|
4
/ \
5 8
/ \
6 9
/ \
7 10
The sequence is an equivalent of A005195 (number of forests with n unlabeled nodes), but made from trees that don't have the unlabeled 10-node graph shown above as a subgraph. This is described in the comment of A300576 and there is also a link to Christian Perfect's website.
In order to find a term of the current sequence, the number of trees containing the shown subgraph must be subtracted from the total number A000055. For n = 10 this is exactly one, for n = 11 it is trivially 4 and for n = 12 it is 19 (A130132).
The marked illustrations from the Steinbach graph catalog show these manually counted tree graphs.
The formulas of A005195 (Euler transform) can then be used to calculate the number of forests if the reduced number of trees A130131 is used instead of A000055. (End)
a(0) = 1: the empty graph is a Tom graph, since Jerry cannot hide from Tom. - Rainer Rosenthal, Mar 01 2020
|
|
|
LINKS
|
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 4 cases for 11 nodes.
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 19 cases for 12 nodes.
|
|
|
FORMULA
|
a(n) <= A005195(n) with equality only for n in {1, ..., 9}.
|
|
|
EXAMPLE
|
The graph
1---2---3
is a Tom graph: Tom can follow the sequence 2, 2 to guarantee that he catches Jerry.
The graph
1
/ \
2---3
is not a Tom graph: Jerry always has 2 vertices to go to, and whatever vertex Tom picks, Jerry can choose another to evade Tom.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
