Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
infinite graph; end; end-faithful; spanning tree; multiplicity
infinite graph; end; end-faithful; spanning tree; multiplicity
Summary:
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$.
References:
[1] N. Bourbaki: Topologie Générale. Chapitre 9. Hermann, Paris, 1958. MR 0173226
[2] H. Freudenthal: Über die Enden diskreter Räume und Gruppen. Comment. Math. Helv. 17 (1944), 1–38. DOI 10.1007/BF02566233 | MR 0012214
[3] G. Hahn and J. Širáň: Three remarks on end-faithfulness. Finite and Infinite Combinatorics in Sets and Logic, N. Sauer et al. (eds.), Kluwer, Dordrecht, 1993, pp. 125–133. MR 1261200
[4] R. Halin: Über unendliche Wege in Graphen. Math. Ann. 157 (1964), 125–137. DOI 10.1007/BF01362670 | MR 0170340 | Zbl 0125.11701
[5] R. Halin: Über die Maximalzahl fremder unendlicher Wege in Graphen. Math. Nachr. 30 (1965), 63–85. DOI 10.1002/mana.19650300106 | MR 0190031 | Zbl 0131.20904
[6] R. Halin: Die Maximalzahl fremder zweiseitig unendliche Wege in Graphen. Math. Nachr. 44 (1970), 119–127. DOI 10.1002/mana.19700440109 | MR 0270953
[7] H. Hopf: Enden offener Raüme und unendliche diskontinuierliche Gruppen. Comment. Math. Helv. 15 (1943), 27–32. MR 0007646
[8] H. A. Jung: Connectivity in Infinite Graphs. Studies in Pure Mathematics, L. Mirsky (ed.), Academic Press, New York-London, 1971, pp. 137–143. MR 0278982 | Zbl 0217.02603
[9] F. Laviolette and N. Polat: Spanning trees of countable graphs omitting sets of dominated ends. Discrete Math. 194 (1999), 151–172. MR 1657074
[10] N. Polat: Développements terminaux des graphes infinis. I. Arbres maximaux coterminaux. Math. Nachr. 107 (1982), 283–314. DOI 10.1002/mana.19821070124 | MR 0695755 | Zbl 0536.05043
[11] N. Polat: Développements terminaux des graphes infinis. III. Arbres maximaux sans rayon, cardinalité maximum des ensembles disjoints de rayons. Math. Nachr. 115 (1984), 337–352. DOI 10.1002/mana.19841150126 | MR 0755288 | Zbl 0536.05045
[12] N. Polat: Spanning trees of infinite graphs. Czechoslovak Math. J. 41 (1991), 52–60. MR 1087622 | Zbl 0793.05054
[13] N. Polat: Ends and multi-endings. I. J. Combin. Theory Ser. B 67 (1996), 86–110. DOI 10.1006/jctb.1996.0035 | MR 1385385 | Zbl 0855.05051
[14] N. Polat: Ends and multi-endings. II. J. Combin. Theory Ser. B 68 (1996), 56–86. DOI 10.1006/jctb.1996.0057 | MR 1405706 | Zbl 0855.05052
[15] P. Seymour and R. Thomas: An end-faithful spanning tree counterexample. Discrete Math. 95 (1991). DOI 10.1016/0012-365X(91)90344-2 | MR 1045600
[16] J. Širáň: End-faithful forests and spanning trees in infinite graphs. Discrete Math. 95 (1991), 331–340. DOI 10.1016/0012-365X(91)90345-3 | MR 1141946
[17] C. Thomassen: Infinite connected graphs with no end-preserving spanning trees. J. Combin. Theory Ser. B 54 (1992), 322–324. DOI 10.1016/0095-8956(92)90059-7 | MR 1152455 | Zbl 0753.05030
[18] B. Zelinka: Spanning trees of locally finite graphs. Czechoslovak Math. J. 39 (1989), 193–197. MR 0992126 | Zbl 0679.05023
Search
Partner of
