I'm working on the problem of finding all the isomorphism classes of 3-regular (each node has exactly 3 neighbours) fully connected tree (no loops) graphs with $n$ stray edges. This seems like a problem that would have been done before but I'm not sure of the terminology to search for it.
We may rephrase this as "number of tree graphs with n nodes of degree 1 (I'll call stray nodes) and all other nodes of degree 3". All isomorphisms are then generated by permutations of the $n$ stray nodes under the symmetric group $S_n$.
Some examples: I draw the stray nodes in light grey and label them $\{1\dots n\}$. The cases where $n=1$ and $n=2$ are degenerate.
- For $n=3$, $n=4$ and $n=5$ there is only one such graph.
- For all $n$ there is always a $K$ shaped graph
- For $n=6$ there are two. The corresponding $K$ graph described above and also this one.
What I've done so far
I have attempted to consider this algebraically. All nodes being degree 3 allows us to think of connecting two edges as a binary operation on the edges. As in we may consider connecting two edges as $$(\_,\_): E \times E \mapsto E$$
This product commutes but is not associative. We also need a relation between edges $\sim$ which identifies two edges and connects their respective nodes. This relation is symmetric. If we then start with our $n$ stray edges, which I'll index with $\{1 \dots n\}$ also, our graph may be considered as a nested product of these edges with at least two edges related by $\sim$. For example the graph for $n=5$ would be
$$(((1,2),3),4) \sim 5 $$
and for $n=6$ the case that isn't the $K$ graph would be $$(((1,2),(3,4)),5) \sim 6$$
Here I work through the above example and label the edges as I go. There are many equivalent ways to write the same graph in this bracketing notation. We see that we can omit the $\sim n$ part if we are forced to choose a bracketing similar to the last two examples where on one side of $\sim$ is just $n$. Using this restriction we can equivalently write the $n=5$ graph as $$(((1,2),3),4)$$ where the $\sim 5$ is inferred. An isomorphic graph can be constructed by acting with $S_n$ on the bracket in the obvious way. We may then omit the numbers to represent an isomorphism class. For example for the $n=5$ graph $$(((\bullet, \bullet),\bullet),\bullet)$$
Remember this product is still commutative so $$(((\bullet, \bullet),\bullet),\bullet) = ((\bullet, (\bullet, \bullet)),\bullet)$$ for example.
Unfortunately this doesn't work as $((\bullet,\bullet),(\bullet,\bullet))$ and $(((\bullet, \bullet),\bullet),\bullet)$ are isomorphic graphs but not equal bracketings. I'm not sure if there's any way to fix this idea.