A124003 -id:A124003 - cp's OEIS frontend

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

Martin Fuller, Dec 08 2006

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.

			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

P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957), 961-968.
B. McMullen, Graph reconstruction numbers.
Wikipedia, Reconstruction conjecture.

Cf. A124003, A000088, A006652-A006655.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs