0

I'm not familiar with the terminology of graph theory, since I have only worked with directed graphs the way they are usually defined in algebra: $$E= (E^0, E^1, r, s)$$ where $E^0$ is the set of vertices, $E^1$ is the set of edges, $r: E^1 \to E^0$ is a function assigning a range to every edge, and $S: E^1 \to E^0$ is a function assigning a source to every edge.

I am interested to know the meaning of this sequence, the number of oriented trees with $n$ nodes. Can anybody help?

Questions:

  • Does an oriented tree have a single source and multiple sinks, or may it have multiple sources and multiple sinks?

  • Is a node the same thing as a vertex?

  • When are two oriented trees considered the same?

Stanley
  • 3,094

1 Answers1

3

The oriented trees in the sequence to which you linked are unlabelled and unrooted: they are simply unlabelled trees with an orientation specified for each edge. Nodes are indeed vertices. Two of these trees are isomorphic if there is an isomorphism between their underlying unoriented trees that preserves the orientations of the edges.

For example, the $8$ oriented trees on $4$ nodes are the $4$ with underlying unoriented tree

                    *---*---*---*

and the $4$ with underlying unoriented tree

                    *---*---*  
                        |  
                        *

The first four are: $$\begin{align*} &*\longrightarrow *\longrightarrow *\longrightarrow *\\ &*\longrightarrow *\longrightarrow *\longleftarrow *\\ &*\longrightarrow *\longleftarrow *\longrightarrow *\\ &*\longleftarrow *\longleftarrow *\longrightarrow * \end{align*}$$

No two of these are isomorphic as directed graphs, and every orientation of a chain of $4$ vertices is isomorphic to one of these four. The other $4$ isomorphism classes can be distinguished by the in-degree (or out-degree) of the central vertex: it can have in-degree $0,1,2$, or $3$, and each of those in-degrees corresponds to a single oriented graph, since the leaves are indistinguishable.

Every leaf will necessarily be either a source or a sink, since either its out-degree or its in-degree must be $0$. There may be internal sources or sinks, but there need not be.

Brian M. Scott
  • 616,228
  • Hi @Brian. Is there a well-known name for (directed) tree graphs that have exactly one sink? For example, $ \begin{align} \bullet \to &\bullet \to \bullet \to \bullet \ & \uparrow \end{align}$ – Stanley Sep 18 '16 at 17:27
  • @Stanley: I don’t know of such a term, but it’s not my field, so there might very well be one. – Brian M. Scott Sep 18 '16 at 18:04