<p>I'm still not sure that I completely understand the problem domain, but here's a few suggestions:</p>

<ul>
<li>The depth of each leaf.</li>
<li>The difference between min and max number of children at each depth.</li>
<li>The number of leaves below each node.</li>
<li>The difference between the depths of the left and right subtrees for an in-order traversal.</li>
<li>The weights required to build a Huffman tree of the same structure.</li>
</ul>

CC BY-SA 3.0
2013-10-06T10:17:52.007Z
2013-10-06T10:17:52.007Z
David Cummins
<p>I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number of vertices is less than 20) and degree is upper bounded by 4, such that we can reconstruct the tree form the encoding, decoding is not necessary to be unique but low degeneracy is expected. Currently, I am given the number of vertices at various distance from the root, say $d = [d_1, d_2, ..., d_k]$ where $d_i$ is the number of vertices at distance $i$ from root. However, the number of tree satisfying this condition is very large. I am looking for other representation (as an alternative to $d$) of tree which will be more suitable for reconstruction, may be approximately. I would prefer the representation which is hierarchical in the sense that, first few information are more constrained and informative, and others are gradually less so. For example, here $d_1$ gives complete information on number of nodes at level 1, there is slight degeneracy in constructing level two nodes from $d_2$, etc. My focus is on approximate reconstruction rather than canonical encoding. </p>

CC BY-SA 3.0
2013-10-04T22:26:36.640Z
It's quite difficult to provide an answer without knowing what information is available. For example, if the data for these comes from some sort of experiment, only certain kinds of data may be available. I may suggest a representation that uses the ratio of leaves to inner nodes for arbitrary example, but it may be unavailable.
David Cummins
CC BY-SA 3.0
2013-10-05T07:39:18.677Z
@DavidCummins these graphs are molecular graphs. First I need to code a molecule preferably into a single number and then reconstruct, with low degenearcy, the graph from the number.
DurgaDatta
CC BY-SA 3.0
2013-12-06T01:23:49.170Z
What is the problem with, for example, having the vertices of the tree labelled and simply storing the parent of each vertex?
Andrew D. King
CC BY-SA 3.0
2013-12-06T05:15:51.327Z
The representation should be invariant of labeling, and should preferably result in a single real number or vector of dimension at most tree height.
DurgaDatta
CC BY-SA 3.0
2013-12-08T13:58:33.463Z
What do you mean by degeneracy? Did you mean [degeneracy](http://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) in graph theory? In this case degeneracy of tree is one, even if your molecule structure is planar, its degeneracy is five. I think you mean bounded maximum degree not degeneracy. Also what's wrong if you just make a complete binary,... tree. I mean the structure that you already know, then the only information that you need is the number of nodes.
Saeed
<graph-theory><graph-algorithms><co.combinatorics><tree>
Representation suitable for reconstruction of a tree with bounded degree
DurgaDatta
# Representation suitable for reconstruction of a tree with bounded degree

(Asked by: username_0 on 2013-10-02)

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number of vertices is less than 20) and degree is upper bounded by 4, such that we can reconstruct the tree form the encoding, decoding is not necessary to be unique but low degeneracy is expected. Currently, I am given the number of vertices at various distance from the root, say $d = [d\_1, d\_2, ..., d\_k]$ where $d\_i$ is the number of vertices at distance $i$ from root. However, the number of tree satisfying this condition is very large. I am looking for other representation (as an alternative to $d$) of tree which will be more suitable for reconstruction, may be approximately. I would prefer the representation which is hierarchical in the sense that, first few information are more constrained and informative, and others are gradually less so. For example, here $d\_1$ gives complete information on number of nodes at level 1, there is slight degeneracy in constructing level two nodes from $d\_2$, etc. My focus is on approximate reconstruction rather than canonical encoding.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, tree

> **Comments:**
> **username_1**: It's quite difficult to provide an answer without knowing what information is available. For example, if the data for these comes from some sort of experiment, only certain kinds of data may be available. I may suggest a representation that uses the ratio of leaves to inner nodes for arbitrary example, but it may be unavailable.  
> **username_0**: @DavidCummins these graphs are molecular graphs. First I need to code a molecule preferably into a single number and then reconstruct, with low degenearcy, the graph from the number.  
> **username_2**: What is the problem with, for example, having the vertices of the tree labelled and simply storing the parent of each vertex?  
> **username_0**: The representation should be invariant of labeling, and should preferably result in a single real number or vector of dimension at most tree height.  
> **username_3**: What do you mean by degeneracy? Did you mean [degeneracy](http://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) in graph theory? In this case degeneracy of tree is one, even if your molecule structure is planar, its degeneracy is five. I think you mean bounded maximum degree not degeneracy. Also what's wrong if you just make a complete binary,... tree. I mean the structure that you already know, then the only information that you need is the number of nodes.  

---

## 1 answers

### Answer by username_1 on 2013-10-06. Score: 0

I'm still not sure that I completely understand the problem domain, but here's a few suggestions:

* The depth of each leaf.
* The difference between min and max number of children at each depth.
* The number of leaves below each node.
* The difference between the depths of the left and right subtrees for an in-order traversal.
* The weights required to build a Huffman tree of the same structure.


---

