Articles of trees

Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. EDIT: I am now exploring options other than the one below. Also in my particular domain I […]

Understanding countable ordinals (as trees, step by step)

Even though ordinal numbers – considered as transitive sets – are perfect non–trees, it is worth (and natural) to visualize them as trees, starting from the finite ones which are given as non-branching trees of finite height: There are some crucial steps in the process of “understanding” larger ordinals, resp. when considering them as trees1. […]

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node and the children of each node are ordered from left to right. Can someone […]

What's the rank of this well founded relation?

Definition A tree is an ordered list of trees. (N.B these are finite objects and there is a very simple computable bijection of them with $\mathbb N$) Examples [] and [[],[],[]] and [[[]],[[],[],[]],[[],[],[[]]]] but it’s much better to think of them like this (can ignore the colors for now) I was wondering what is the […]

Characterization of hierarchically clustered graphs

There is a strong relationship between (rooted) trees and hierarchically clustered graphs as can be seen here: The tree – consisting of circles (green = the root, blue, red, black = the leaves) and thin lines – can be seen as the result of a hierarchical cluster analysis of the graph consisting of the black […]

On the number of caterpillars

A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ vertices, $n\geq3$? (It should use Polya’s theorem)

How to find non-isomorphic trees?

“Draw all non-isomorphic trees with 5 vertices.” I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can’t figure out how they have come to their answer. How exactly do you find how many non-isomorphic trees there are and what they look like? Thanks for your time

Show that a graph has a unique MST if all edges have distinct weights

This question already has an answer here: Show that there's a minimum spanning tree if all edges have different costs 3 answers

EGF of rooted minimal directed acylic graph

I am trying to find the exponential generating function of directed minimal acyclic graphs (which I now call dag), where every non-leaf node has two outgoing edges. Context: A simple tree compression algorithm consists of saving repeated subtrees only once. Further occurrences of repeated trees are simply linked to the first occurrence. This way one […]

Is the graceful labeling conjecture still unsolved?

From the Wikipedia article on graceful labeling: … A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel-Kotzig conjecture is also known as the “graceful labeling conjecture”. … Is the conjecture still unsolved? (for example I found Dhananjay […]