Topological complexity of graphs and their spanning trees
type: Item
instance of: scholarly article
title: Topological complexity of graphs and their spanning trees
zbMATH Open document ID: 0837.05046
DOI: 10.1007/BF01874350
author: Ronny Nahum
author: Samy Zafrany
published in: Acta Mathematica Hungarica
publication date: 1996-01-01T00:00:00Z
review text: 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 \(\sigma\)-analytic if \(\vec E\) belongs to the \(\sigma\)-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 \(\sigma\)-analytic, \(V(F)\) is analytic, and \(F\) has countably many connectivity components, then \(F\) can be extended into a \(\sigma\)- analytic spanning tree of \(G\) (Theorem 1.2). In Section 2 we study weighted graphs. A weighted graph is a triple \(W = (G, {\mathbf w}, \lambda)\) such that \(G = (V,E)\) is a simple graph, \(\lambda\) is an ordinal, and \({\mathbf w} : E \to \lambda\). For every \(\beta < \lambda\), let \(G^\beta\) be the subgraph of \(G\) consisting of all edges \(u \in E\) such that \({\mathbf w} (u) = \beta\). 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 \(\lambda\) are finite. In the infinite case, \textit{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 weight…
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 755489
zbMATH Keywords: perfect Polish space
zbMATH Keywords: topological complexity
zbMATH Keywords: spanning trees
zbMATH Keywords: components
zbMATH Keywords: weighted graph
MaRDI profile type: Publication
cites work: Separation principles in the hierarchies of classical and effective descriptive set theory
cites work: Infinite matching theory
cites work: The cover-index of infinite graphs
cites work: Q5775449
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Q3041212
description: scientific article; zbMATH DE number 755489