|
%I #94 Jul 05 2020 13:16:38
%S 1,1,2,3,6,10,20,37,76,153,328,705,1576,3551,8179,18980,44559,105111,
%T 249426,593484,1416269,3384581,8099819,19398194,46487665,111447044,
%U 267260387,641022947,1537706522,3688974818,8850411933,21234093757,50946316856,122234742311
%N Number of Tom graphs with n vertices.
%C 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.
%C 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:
%C 1
%C |
%C 2
%C |
%C 3
%C |
%C 4
%C / \
%C 5 8
%C / \
%C 6 9
%C / \
%C 7 10
%C From _Hugo Pfoertner_, Feb 20 2020 (Start):
%C 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.
%C 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).
%C The marked illustrations from the Steinbach graph catalog show these manually counted tree graphs.
%C 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)
%C a(0) = 1: the empty graph is a Tom graph, since Jerry cannot hide from Tom. - _Rainer Rosenthal_, Mar 01 2020
%H Seiichi Manyama, <a href="/A331693/b331693.txt">Table of n, a(n) for n = 0..2000</a>
%H Project Euler, <a href="https://projecteuler.net/problem=690">Problem 690: Tom and Jerry</a>
%H Peter Steinbach, <a href="/A331693/a331693.pdf">Simple Graphs - Trees</a>, illustrations of the graphs, including an added marking of the relevant 4 cases for 11 nodes.
%H Peter Steinbach, <a href="/A331693/a331693_1.pdf">Simple Graphs - Trees</a>, illustrations of the graphs, including an added marking of the relevant 19 cases for 12 nodes.
%F a(n) <= A005195(n) with equality only for n in {1, ..., 9}.
%e The graph
%e 1---2---3
%e is a Tom graph: Tom can follow the sequence 2, 2 to guarantee that he catches Jerry.
%e The graph
%e 1
%e / \
%e 2---3
%e 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.
%Y Cf. A000055, A005195, A130131, A130132, A300576.
%K nonn
%O 0,3
%A _Bobby Jacobs_, Jan 24 2020
%E a(11)-a(12) from _Hugo Pfoertner_, Feb 20 2020
%E a(0), a(13)-a(33) from _Rainer Rosenthal_, Feb 29 2020
| 