MathOverflow is a question and answer site for professional mathematicians. 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. The property which I'm singling out as being suggestive of continuity is in this case the preservation of connectivity of subsets.

My question is: have people approached subjects such as tree-decompositions (or path decompositions, etc.) explicitly from a point of view of continuous functions before, and has it proven a useful way of presenting results? For instance, is there any 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?

(I posted this question previously on Math.SE, without any answers.)

share|cite|improve this question

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.