A124002 -id:A124002 - cp's OEIS frontend

A124003 Triangle T(n,k) of the number of unlabeled graphs on n nodes with universal reconstruction number k, 3<=k<=n. URN(G) is the minimum size for which all multisubsets of vertex-deleted subgraphs of G can uniquely reconstruct G up to isomorphism.

3, 2, 9, 7, 19, 8, 8, 56, 90, 2, 16, 496, 520, 12, 0, 266, 8308, 3584, 284, 4, 0, 45186, 199247, 28781, 1434, 20, 0, 0, 6054148, 5637886, 301530, 10686, 914, 4, 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 URN and so sum(k=3,n,T(n,k))==A000088(n) for all n>=3.

			Triangle begins
        3
        2       9
        7      19      8
        8      56     90     2
       16     496    520    12   0
      266    8308   3584   284   4 0
    45186  199247  28781  1434  20 0 0
  6054148 5637886 301530 10686 914 4 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. A124002, A000088, A006652-A006655.

cp's OEIS Frontend

A124003 Triangle T(n,k) of the number of unlabeled graphs on n nodes with universal reconstruction number k, 3<=k<=n. URN(G) is the minimum size for which all multisubsets of vertex-deleted subgraphs of G can uniquely reconstruct G up to isomorphism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs