| Title:
|
Multi-faithful spanning trees of infinite graphs (English) |
| Author:
|
Polat, Norbert |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
51 |
| Issue:
|
3 |
| Year:
|
2001 |
| Pages:
|
477-492 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
infinite graph |
| Keyword:
|
end |
| Keyword:
|
end-faithful |
| Keyword:
|
spanning tree |
| Keyword:
|
multiplicity |
| MSC:
|
05C05 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1079.05516 |
| idMR:
|
MR1851542 |
| . |
| Date available:
|
2009-09-24T10:44:31Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127664 |
| . |
| Reference:
|
[1] N. Bourbaki: Topologie Générale. Chapitre 9.Hermann, Paris, 1958. MR 0173226 |
| Reference:
|
[2] H. Freudenthal: Über die Enden diskreter Räume und Gruppen.Comment. Math. Helv. 17 (1944), 1–38. MR 0012214, 10.1007/BF02566233 |
| Reference:
|
[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 |
| Reference:
|
[4] R. Halin: Über unendliche Wege in Graphen.Math. Ann. 157 (1964), 125–137. Zbl 0125.11701, MR 0170340, 10.1007/BF01362670 |
| Reference:
|
[5] R. Halin: Über die Maximalzahl fremder unendlicher Wege in Graphen.Math. Nachr. 30 (1965), 63–85. Zbl 0131.20904, MR 0190031, 10.1002/mana.19650300106 |
| Reference:
|
[6] R. Halin: Die Maximalzahl fremder zweiseitig unendliche Wege in Graphen.Math. Nachr. 44 (1970), 119–127. MR 0270953, 10.1002/mana.19700440109 |
| Reference:
|
[7] H. Hopf: Enden offener Raüme und unendliche diskontinuierliche Gruppen.Comment. Math. Helv. 15 (1943), 27–32. MR 0007646 |
| Reference:
|
[8] H. A. Jung: Connectivity in Infinite Graphs.Studies in Pure Mathematics, L. Mirsky (ed.), Academic Press, New York-London, 1971, pp. 137–143. Zbl 0217.02603, MR 0278982 |
| Reference:
|
[9] F. Laviolette and N. Polat: Spanning trees of countable graphs omitting sets of dominated ends.Discrete Math. 194 (1999), 151–172. MR 1657074 |
| Reference:
|
[10] N. Polat: Développements terminaux des graphes infinis. I. Arbres maximaux coterminaux.Math. Nachr. 107 (1982), 283–314. Zbl 0536.05043, MR 0695755, 10.1002/mana.19821070124 |
| Reference:
|
[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. Zbl 0536.05045, MR 0755288, 10.1002/mana.19841150126 |
| Reference:
|
[12] N. Polat: Spanning trees of infinite graphs.Czechoslovak Math. J. 41 (1991), 52–60. Zbl 0793.05054, MR 1087622 |
| Reference:
|
[13] N. Polat: Ends and multi-endings. I.J. Combin. Theory Ser. B 67 (1996), 86–110. Zbl 0855.05051, MR 1385385, 10.1006/jctb.1996.0035 |
| Reference:
|
[14] N. Polat: Ends and multi-endings. II.J. Combin. Theory Ser. B 68 (1996), 56–86. Zbl 0855.05052, MR 1405706, 10.1006/jctb.1996.0057 |
| Reference:
|
[15] P. Seymour and R. Thomas: An end-faithful spanning tree counterexample.Discrete Math. 95 (1991). MR 1045600, 10.1016/0012-365X(91)90344-2 |
| Reference:
|
[16] J. Širáň: End-faithful forests and spanning trees in infinite graphs.Discrete Math. 95 (1991), 331–340. MR 1141946, 10.1016/0012-365X(91)90345-3 |
| Reference:
|
[17] C. Thomassen: Infinite connected graphs with no end-preserving spanning trees.J. Combin. Theory Ser. B 54 (1992), 322–324. Zbl 0753.05030, MR 1152455, 10.1016/0095-8956(92)90059-7 |
| Reference:
|
[18] B. Zelinka: Spanning trees of locally finite graphs.Czechoslovak Math. J. 39 (1989), 193–197. Zbl 0679.05023, MR 0992126 |
| . |
