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.

enter image description here

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

enter image description here

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


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.

  • $\begingroup$ Thank you and sorry for late acceptance of the answer. I posted the question a little before I left for vacations. These structures seem to be quite interesting. $\endgroup$ – Kristina Dedndreaj Aug 22 '18 at 8:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.