A331693 Number of Tom graphs with n vertices.

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

Offset: 0

Author

Bobby Jacobs, Jan 24 2020

Keywords

• nonn

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

From Hugo Pfoertner, Feb 20 2020 (Start):

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

Examples

			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.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..2000
• Project Euler, Problem 690: Tom and Jerry
• 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.

Crossrefs

Cf. A000055, A005195, A130131, A130132, A300576.

Formula

a(n) <= A005195(n) with equality only for n in {1, ..., 9}.

Extensions

a(11)-a(12) from Hugo Pfoertner, Feb 20 2020

a(0), a(13)-a(33) from Rainer Rosenthal, Feb 29 2020