Are these trees useful and how are they named in the literature

Question

I am working in a project with trees and it turns out that the specific problem I am trying to attack is easy on some types of trees. If we consider the rooted layout of the tree with the root being the center (or one of the centers if there are two) then each vertex of each level (except the last one) has at least a child which is leaf.

A more specific structure within this class would be those trees which look like the following example.

Is there any name for these kind of trees? And most importantly, are these structures useful in computer science or in any other science?

Answer 1

I have seen these type of trees arise in structural graph theory, where for some particular class of graphs we are interested in a decomposition theorem. One example of a decomposition theorem is the following:

Theorem (Dirac). If $G$ is a chordal graph, then either $G$ is complete or it has a clique cutset.

From these decomposition theorems, we can construct decomposition trees. Say we wish to find a minimum vertex colouring of a graph $G$. Then we can construct a decomposition tree whose root is the original graph $G$, and whose children are so-called blocks of decomposition. This is repeated until we obtain (induced sub-)graphs that have no clique cutset. These are called atoms, and are the leaves of the tree. To solve the vertex colouring problem, we can solve it on these atoms and then propagate the result up to the top of the tree - to the original graph.

If a graph has a clique cutset, then in fact it has an extreme clique cutset. An extreme clique cutset is a clique cutset which produces an atom in the decomposition tree. Thus if at each non-leaf node of the decomposition tree we remove an extreme clique cutset, we obtain a leaf. This gives the type of trees that you are interested in.

Knowing the structure of this decomposition tree is useful - it tells us that there are at most $n-1$ leaves in a clique cutset decomposition tree for a graph on $n$ vertices.

See Section 3 of The world of hereditary graph classes viewed through Truemper configurations (Vuskovic, 2013) for more information on these decomposition trees.