|
Search: id:A124003
|
|
|
| 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. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
3,1
|
|
|
COMMENT
|
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
|
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: A021756 A084398 A118306 this_sequence A159588 A118045 A081233
Adjacent sequences: A124000 A124001 A124002 this_sequence A124004 A124005 A124006
|
|
KEYWORD
|
hard,more,nice,nonn,tabl
|
|
AUTHOR
|
Martin Fuller (martin_n_fuller(AT)btinternet.com), Dec 08 2006
|
|
|
Search completed in 0.002 seconds
|
