Bag intersections to create trees from bigger bags

Hi

I'm currently pondering the problem of how to count the number of
isomorphic graphs (well trees actually) that you will obtain if you
intersect bags of the nodes with the tree.

Each bag basically contains all the nodes in a given sub-tree, and
conceptually speaking, each bag tells me that all of it's components
must be connected to each other through some path. The connections
would be acyclic.

The reasoning I'm thinking is that if a bag represents a particular
sub-tree, then if you keep iteratively intersecting the bags with the
tree, you will keep introducing restrictions as to the number of nodes
that a node can connect to, and you will eventually end up with a graph
looking like the original tree.

A further question I'm trying to answer is how many bags are needed so
that you can uniquely reconstruct a tree from the intersection of each
of the bags. Does anyone have any pointers to papers or textbooks, or
google keywords that might help me find an answer to these problems?

I'm really just looking for good starting points to dig into this
problem, because I'm lacking the knowledge in graph theory to be able
to properly describe this, and I need to do that before I can even
think about solving it.

Hiren

.

Relevant Pages