login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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 (list; table; graph; refs; listen; history; text; internal format)
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 URN 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

        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

CROSSREFS

Cf. A124002, A000088, A006652-A006655.

Sequence in context: A084398 A118306 A237651 * A159588 A321572 A118045

Adjacent sequences:  A124000 A124001 A124002 * A124004 A124005 A124006

KEYWORD

hard,more,nice,nonn,tabl

AUTHOR

Martin Fuller, Dec 08 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 22:44 EDT 2019. Contains 328291 sequences. (Running on oeis4.)