2
$\begingroup$

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.)

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.