Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:
- For every edge $\{v_1,v_2\} \in E$, there exists a node $n$ of $T$ such that $v_1,v_2 \in \lambda(n)$.
- For every vertex $v \in V$, the set $\{n \in T \mid v \in n\}$ forms a connected subtree of $T$.
For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a tree-decomposition with clique interfaces a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:
- For every two adjacent nodes $n_1$ and $n_2$ of the tree decomposition $T$, we require that the interface $\lambda(n_1) \cap \lambda(n_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n_1$ and $n_2$, we must have $\{a, b\} \in E$.
As usual, the width of such a decomposition is $max_{n \in T}|\lambda(n)|-1$ and the width of $G$ is the minimal width of such a decomposition. Note that, of course, the width of $G$ according to this definition is necessarily greater than its treewidth in the usual sense.
My question is to know if this notion of width has already been studied and has an established name. In particular, I am interested in alternative characterization of graphs whose width is low in this sense, in the complexity of computing it, etc.
This could be related to the notion of $k$-trees. In k-trees, we impose in tree decompositions that $\lambda(n)$ forms a clique for all $n$ and that the interfaces are of size $k$. However not all graphs have such a decomposition, while for the notion that I propose, all graphs would have a decomposition (at worst the trivial one with width $|V|-1$) so it looks like this notion could have been studied in a general context.
