Geodesic
Multi-faithful spanning trees of infinite graphs
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 3, pp. 477-492 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C05, 05C99
Keywords: infinite graph; end; end-faithful; spanning tree; multiplicity 
@article{CMJ_2001_51_3_a3,
     author = {Polat, Norbert},
     title = {Multi-faithful spanning trees of infinite graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {477--492},
     year = {2001},
     volume = {51},
     number = {3},
     mrnumber = {1851542},
     zbl = {1079.05516},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_3_a3/}
}
TY  - JOUR
AU  - Polat, Norbert
TI  - Multi-faithful spanning trees of infinite graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2001
SP  - 477
EP  - 492
VL  - 51
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2001_51_3_a3/
LA  - en
ID  - CMJ_2001_51_3_a3
ER  - 
%0 Journal Article
%A Polat, Norbert
%T Multi-faithful spanning trees of infinite graphs
%J Czechoslovak Mathematical Journal
%D 2001
%P 477-492
%V 51
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2001_51_3_a3/
%G en
%F CMJ_2001_51_3_a3
Polat, Norbert. Multi-faithful spanning trees of infinite graphs. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 3, pp. 477-492. http://geodesic.mathdoc.fr/item/CMJ_2001_51_3_a3/

[1] N.  Bourbaki: Topologie Générale. Chapitre 9. Hermann, Paris, 1958. | MR

[2] H.  Freudenthal: Über die Enden diskreter Räume und Gruppen. Comment. Math. Helv. 17 (1944), 1–38. | DOI | MR

[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

[4] R.  Halin: Über unendliche Wege in Graphen. Math. Ann. 157 (1964), 125–137. | DOI | MR | Zbl

[5] R.  Halin: Über die Maximalzahl fremder unendlicher Wege in Graphen. Math. Nachr. 30 (1965), 63–85. | DOI | MR | Zbl

[6] R.  Halin: Die Maximalzahl fremder zweiseitig unendliche Wege in Graphen. Math. Nachr. 44 (1970), 119–127. | DOI | MR

[7] H.  Hopf: Enden offener Raüme und unendliche diskontinuierliche Gruppen. Comment. Math. Helv. 15 (1943), 27–32. | MR

[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 | Zbl

[9] F.  Laviolette and N.  Polat: Spanning trees of countable graphs omitting sets of dominated ends. Discrete Math. 194 (1999), 151–172. | MR

[10] N.  Polat: Développements terminaux des graphes infinis. I. Arbres maximaux coterminaux. Math. Nachr. 107 (1982), 283–314. | DOI | MR | Zbl

[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 | MR | Zbl

[12] N.  Polat: Spanning trees of infinite graphs. Czechoslovak Math. J. 41 (1991), 52–60. | MR | Zbl

[13] N.  Polat: Ends and multi-endings. I. J.  Combin. Theory Ser. B 67 (1996), 86–110. | DOI | MR | Zbl

[14] N.  Polat: Ends and multi-endings.  II. J.  Combin. Theory Ser. B 68 (1996), 56–86. | DOI | MR | Zbl

[15] P.  Seymour and R.  Thomas: An end-faithful spanning tree counterexample. Discrete Math. 95 (1991). | DOI | MR

[16] J.  Širáň: End-faithful forests and spanning trees in infinite graphs. Discrete Math. 95 (1991), 331–340. | DOI | MR

[17] C.  Thomassen: Infinite connected graphs with no end-preserving spanning trees. J.  Combin. Theory Ser. B 54 (1992), 322–324. | DOI | MR | Zbl

[18] B.  Zelinka: Spanning trees of locally finite graphs. Czechoslovak Math. J. 39 (1989), 193–197. | MR | Zbl