cp's OEIS Frontend

A331693 Number of Tom graphs with n vertices.

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