Multi-faithful spanning trees of infinite graphs

Polat, Norbert

Czechoslovak Mathematical Journal, Tome 51 (2001) no. 3, pp. 477-492.

Résumé

For an end $\tau $ and a tree $T$ of a graph $G$ we denote respectively by $m(\tau )$ and $m_{T}(\tau )$ the maximum numbers of pairwise disjoint rays of $G$ and $T$ belonging to $\tau $, and we define $\mathop {\mathrm tm}(\tau ) := \min \lbrace m_{T}(\tau )\: T \text{is} \text{a} \text{spanning} \text{tree} \text{of} G \rbrace $. In this paper we give partial answers—affirmative and negative ones—to the general problem of determining if, for a function $f$ mapping every end $\tau $ of $G$ to a cardinal $f(\tau )$ such that $\mathop {\mathrm tm}(\tau ) \le f(\tau ) \le m(\tau )$, there exists a spanning tree $T$ of $G$ such that $m_{T}(\tau ) = f(\tau )$ for every end $\tau $ of $G$.

Détail

Classification : 05C05, 05C99
Keywords: infinite graph; end; end-faithful; spanning tree; multiplicity