Previous |  Up |  Next

Article

Summary:
We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.
References:
[1] H. Freudenthal: Über die Enden diskreter Räume und Gruppe. Comment. Math. Helv. 17 (1944), 1–38. DOI 10.1007/BF02566233 | MR 0012214
[2] G. Hahn and J. Širáň: Three remarks on end-faithfulness. Finite and Infinite Combinatorics in Sets and Logic, N. Sauer et al. (eds.), Kluwer, 1993, pp. 125–133. MR 1261200
[3] R. Halin: Über unendliche Wege in Graphen. Math. Ann. 157 (1964), 125–137. DOI 10.1007/BF01362670 | MR 0170340 | Zbl 0125.11701
[4] H. Hopf: Enden offener Raüme und unendliche diskontinuierliche Gruppen. Comm. Math. Helv. 15 (1943), 27–32. MR 0007646
[5] 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
[6] 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
[7] 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
[8] P. Seymour and R. Thomas: An end-faithful spanning tree counterexample. Discrete Math. 95 (1991), 321–330. DOI 10.1016/0012-365X(91)90344-2 | MR 1045600
[9] 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
[10] 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
Partner of
EuDML logo