History

Please fill in your query. A complete syntax description you will find on the General Help page.
Topological complexity of graphs and their spanning trees. (English)
Acta Math. Hung. 66, No.1-2, 1-10 (1995).
Let $X$ be a perfect Polish space. Let $G = (V,E)$ be a simple graph such that $V \subseteq X$. Let $\vec E = \{(x,y) \mid \{x,y\} \in E\}$. We call $G$ analytic if $\vec E$ is an analytic subset of the perfect Polish space $X \times X$. Similarly, $G$ is $σ$-analytic if $\vec E$ belongs to the $σ$-algebra generated by all the analytic subsets of $X \times X$. Having assigned this topological complexity to $G$, one may ask questions concerning the topological complexity of objects related to $G$. In this paper we study spanning trees. The basic question is: Given the topological complexity of $G$, how simple can a spanning tree of $G$ be? By Zorn’s Lemma, it is easy to show that every forest $F$ in a connected simple graph $G$ can be extended into a spanning tree of $G$, but the proof is not constructive. In Section 1 we show that if $G$ is analytic, $F$ is $σ$-analytic, $V(F)$ is analytic, and $F$ has countably many connectivity components, then $F$ can be extended into a $σ$- analytic spanning tree of $G$ (Theorem 1.2). In Section 2 we study weighted graphs. A weighted graph is a triple $W = (G, {\bold w}, λ)$ such that $G = (V,E)$ is a simple graph, $λ$ is an ordinal, and ${\bold w} : E \to λ$. For every $β< λ$, let $G^β$ be the subgraph of $G$ consisting of all edges $u \in E$ such that ${\bold w} (u) = β$. Here we are looking for a spanning tree of $G$ whose “total weight” is as small as possible. This makes a clear sense in case that $G$ and $λ$ are finite. In the infinite case, {\it Ron Aharoni} [Discrete Math. 95, No. 1-3, 5-22 (1991; Zbl 0763.05074)] gave the definition: $T$ is a minimal spanning tree of $W$ if $T$ is a spanning tree of $G$ and if we replace one edge in $T$ by a lighter edge, then $T$ stops being a spanning tree. First, we prove a purely combinatorial fact: every connected weighted graph has a minimal spanning tree (Theorem 2.2). Then we prove a topological version of this fact: Let $W = (G, {\bold w}, λ)$ be a connected weighted graph where $G$ is an analytic graph, $λ$ is a countable ordinal, and for every $β\in λ$, the graph $G^β$ is analytic and has countably many components. Then $W$ has a $σ$-analytic minimal spanning tree (Theorem 2.4). In Section 3 we show that Theorem 2.4 is optimal. First, we show that an analytic minimal spanning tree for $W$ does not always exist. Second, we show that if $G^β$ has uncountably many components for some $β\in λ$ or $λ$ is uncountable then a $σ$-analytic minimal spanning tree for $W$ does not always exist. Finally, we list some open problems.