Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure:

  1. Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$;

  2. The union $\displaystyle\bigcup X_t$ over $t \in V(T)$ is the whole vertex set $V(G)$;

  3. For each $v \in V(G)$, the set $Y_v := \bigl\{ t \in V(T) \;\;\big|\;\; v \in X_t \bigr\}$ induces a connected subgraph of $T$;

  4. For each edge $uv \in E(G)$, there exists $t \in T$ such that $\{u,v\} \subseteq X_t\,$.

This definition feels to me as though it is secretly involving a notion of continuity: not of a function between a graph $G$ and a tree $T$, but instead of a function $\tau$ that maps (non-empty) sets of vertices $X \subseteq V(G)$ to (non-empty) sets of vertices $Y \subseteq V(T)$, in which connectivity is preserved. This is not a notion of continuity precisely in terms of preserving open sets, but perhaps one can make this connection by coming up with a suitably clever notion of an "open set" in a graph, e.g. involving closed edges.

It's easy to re-formulate the definitions of tree decompositions and tree-widths in terms of a map $\tau: \wp(V(G)) \to \wp(V(T))$ which (a) extends a "basis map" $\tau_1: V(G) \to \wp(V(T))$ by unions, and (b) preserves connectivity of vertex-sets, once one has the idea. In particular, the sets $X_t$ would be a sort of pre-image in $\tau$ of the vertex $t \in V(T)$. My question is: is there any book or introductory reference which approaches the subject of tree-decompositions and tree-widths in this manner, or which discusses graph-theoretic structures in terms of such connectivity-preserving functions on vertex-sets?

share|cite|improve this question
Now crossposted to MathOverflow. – Niel de Beaudrap Feb 1 '13 at 16:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.