Trees in which every vertex is a leaf or adjacent to a leaf

155 Views Asked by At

Does anyone know if the class of trees in which every vertex is either a leaf or adjacent to at least one leaf has been studied? Is there a name for them?

These graphs have come up in my research as a handy way to compute volumes of related polytopes. I'm not actually especially interested in the graphs themselves, but if they are known then I'd like to stay consistent with the existing literature.

1

There are 1 best solutions below

0
On

I think this class (call it $C$) can not be studied rather well. Note that its particular case the caterpillars are of a great interest themselves (at least one often starts proving some theorem about trees beginning from caterpillars, lobsters, etc.). Moreover, the caterpillars are those trees which become paths after removing their leafs. In $C$ the same procedure can lead us to any given tree. Thus the theory of $C$ simply extends the theory of trees $T$ (so equivalent to it since $C\subset T$). I think this can be proved more precisely (using the graph homomorphism), i.e. we can prove that every theorem valid in $T$ has its analogue in $C$.

Example. Let's take some simple theorem about trees say $n=q+1$ where $n$ denotes the number of vertices and $q$ is the number of edges. The corresponding result for $C$ will be $n'=q'+1$ where $n'$ denotes the number of vertices that are not leafs ($V'$) and $q'$ is the number of edges with both ends from $V'$.