|
|
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.
|
|
1
|
|
|
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;
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 ERN and so sum(k=3,n,T(n,k))==A000088(n) for all n>=3.
|
|
LINKS
|
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|