On the construction of tree decompositions of hypercubes

Abstract

There are different concepts regarding to tree decomposition of a graph $G$. For the Hypercube $Q_n$, these concepts have been shown to have many applications. But some diverse papers on this subject make it difficult to follow what is precisely known. In this note first we will mention some known results on the tree decomposition of hypercubes and then introduce new explicit constructions for the previously known and unknown cases.

arXiv commenthttp://www.combinatorialmath.ca/ICA/ICA72.html

Cited by in corpus (1)

• A performance study of some approximation algorithms for minimum dominating set in a graph