What graphs have tree decompositions where the bags containing a vertex all lie on a path?

56 Views Asked by At

My question is about tree decompositions of graphs.

For the unfamiliar, the tree decomposition of a graph $G$ is a tree $T$, where each vertex in $T$ (which are called bags) 'contains' vertices from the graph $G$. There are three defining properties as well:

  1. Every vertex in $G$ is in a bag in $T$;
  2. Every edge $vw$ from $G$ is contained (i.e. the vertices occur together) in at least one bag; and lastly
  3. The bag subgraph containing a vertex $v$ is connected.

Tree decompositions are used to define a useful quantity: the treewidth of a graph. This is just the smallest you can make the size of the maximal sized bag in any tree decomposition of that graph.

My question is about restricting the shapes of the bag subgraphs which contain a vertex. These must always be a tree, as the bags are connected and $T$ is a tree.

However, what happens if all bag subgraphs for the vertices must be paths:

  1. Are there some graphs which don't have such decompositions?
  2. Where there is such a decomposition, is the treewidth on the restricted type of decomposition ever strictly greater than the normal treewidth?
  3. Does this subtype of tree decompositions have a name? Have they been studied by anyone?

Answers so far:

  1. No, throw everything into the same bag.

(Here's an example of such a graph from Wikipedia. link)