|
Search: id:A124002
|
|
|
| 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. |
|
+0
2
|
|
| 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
(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 ERN 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
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: A066199 A103647 A033197 this_sequence A014457 A092511 A045816
Adjacent sequences: A123999 A124000 A124001 this_sequence A124003 A124004 A124005
|
|
KEYWORD
|
hard,more,nice,nonn,tabl
|
|
AUTHOR
|
Martin Fuller (martin_n_fuller(AT)btinternet.com), Dec 08 2006
|
|
|
Search completed in 0.002 seconds
|
