2
$\begingroup$

I am looking for help:

Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is undirected. This will produce a "tree trajectory", like this: $$ \circ \quad \rightarrow\quad \circ - \circ \quad \rightarrow\quad \begin{array}{c} \ \ \ \ \circ - \circ \\ | \\ \circ \end{array} \quad \rightarrow\quad \begin{array}{c} \ \ \ \ \circ - \circ \\ | \\\ \ \ \ \circ - \circ \end{array} $$ Another tree trajectory might look like this: $$ \circ \quad \rightarrow\quad \circ - \circ \quad \rightarrow\quad \begin{array}{c} \ \ \ \ \circ - \circ \\ | \\ \circ \end{array} \quad \rightarrow\quad \begin{array}{c} \circ - \circ \\ | \ \ \backslash \\ \circ \ \ \ \circ \end{array} $$

My questions are as follows:

1) How many possible distinct (non-isomporhic) graphs are there with N nodes and N-1 edges?

It's easy to find this by brute force up to 5: N=1: 1; N=2:1; N=3:1; N=4:2; N=5:3

2) For N nodes, how many different tree trajectories are there connecting the graph with N=1 node to the any graph of N nodes? (i.e., how many distinct tree trajectories are there; a tree trajectory is distinct from all others if for any other tree trajectory, there is at least a single step where the two are not isomorphic.) It's clear not just multiplying the number of non-ismorphic graphs at each step, since past graph topology will constrain future graph topologies.

While a solution would obviously be great, ANY help at all would be appreciated.

$\endgroup$
3
  • 2
    $\begingroup$ The answer to your first question is in OEIS. See here: oeis.org/A000055 $\endgroup$
    – Tony Huynh
    Feb 10 '16 at 19:00
  • $\begingroup$ This was helpful - I should have thought to search unlabeled. Still thinking about question two... $\endgroup$
    – Danny W.
    Feb 11 '16 at 0:07
  • $\begingroup$ A note: This is similar to counting number of Young diagrams of some size, and a trajectory of Young diagrams is just a standard Young tableau.... You can probably encode a trajectory as a linear extension of some poset. $\endgroup$ Feb 16 '16 at 16:26
2
$\begingroup$

The total number of trajectories $T(N)$ (as a function of $N$) appears to be

N   T(N)
1   1
2   1 
3   1 
4   2 
5   4 
6   13 
7   48 
8   235 
9   1297 
10  8628 
11  63902 
12  538454 
13  4973090 
14  50621738 
15  557399709 
16  6636723151
17  84584674076
18  1151419603932
19  16640050320703
20  254656634876886
21  4110614617328251

I've added these counts to the OEIS as sequence A268951.

$\endgroup$
2
  • $\begingroup$ The question is rather ambiguous (isomorphism must be defined more precisely), and your answer does not fit the first few terms given. $\endgroup$
    – F. C.
    Feb 19 '16 at 20:25
  • $\begingroup$ @F.C.: I defined it precisely in the OEIS. What given terms do you refer to? I see only terms given for question 1), but nothing for question 2). My counts are about question 2). $\endgroup$ Feb 19 '16 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.