A124002 Triangle T(n,k) of the number of unlabeled graphs on n nodes with existential reconstruction number k, 3<=k<=n. ERN(G) is the minimum number of vertex-deleted subgraphs of G required to uniquely reconstruct G up to isomorphism.

4, 8, 3, 34, 0, 0, 150, 4, 2, 0, 1044, 0, 0, 0, 0, 12334, 8, 2, 2, 0, 0, 274666, 0, 2, 0, 0, 0, 0, 12005156, 6, 4, 0, 2, 0, 0, 0

Offset

3,1

Comments

The (vertex) Reconstruction Conjecture, due to Kelly and Ulam, states that every graph with three or more vertices is reconstructible up to isomorphism given the multiset of vertex deleted subgraphs. Equivalently, every graph has an ERN and so sum(k=3,n,T(n,k))==A000088(n) for all n>=3.

Links

Table of n, a(n) for n=3..38.

P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957), 961-968.

B. McMullen, Graph reconstruction numbers.

Wikipedia, Reconstruction conjecture.

Example

Triangle begins
         4
         8, 3
        34, 0, 0
       150, 4, 2, 0
      1044, 0, 0, 0, 0
     12334, 8, 2, 2, 0, 0
    274666, 0, 2, 0, 0, 0, 0
  12005156, 6, 4, 0, 2, 0, 0, 0

Crossrefs

Cf. A124003, A000088, A006652-A006655.

Sequence in context: A103647 A372356 A033197 * A014457 A388096 A376546

Adjacent sequences: A123999 A124000 A124001 * A124003 A124004 A124005

Keyword

hard,more,nice,nonn,tabl

Author

Martin Fuller, Dec 08 2006

Status

approved