×

zbMATH — the first resource for mathematics

Locally finite graphs with ends: A topological approach. II: Applications. (English) Zbl 1223.05197
Summary: This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [R. Diestel, “Locally finite graphs with ends: a topological approach,” arXiv:0912.4213]. (For part I see [R. Diestel, “Locally finite graphs with ends: A topological approach. I: Basic theory, ”Discrete Math. 311, No. 15, 1423–1447 (2011; Zbl 1223.05198)]). They are complemented by a third part [“Locally finite graphs with ends: A topological approach. III: Fundamental group and homology,” (to appear), see also the article in the ArXiv ( arXiv:1004.0110v2)] which looks at the theory from an algebraic-topological point of view.
The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.

MSC:
05C63 Infinite graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
Citations:
Zbl 1223.05198
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aharoni, R., Menger’s theorem for countable graphs, J. combin. theory B, 43, 303-313, (1987) · Zbl 0631.05032
[2] R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Invent. Math. (in press). · Zbl 1216.05092
[3] R. Aharoni, E. Berger, A. Georgakopoulos, A. Perlstein, P. Sprüssel, The max-flow min-cut theorem for countable networks, J. Combin. Theory B (in press). · Zbl 1221.05186
[4] Aharoni, R.; Thomassen, C., Infinite highly connected digraphs with no two arc-disjoint spanning trees, J. graph theory, 13, (1989) · Zbl 0665.05023
[5] Archdeacon, D.; Bonnington, P.; Little, C., An algebraic characterization of planar graphs, J. graph theory, 19, 237-250, (1995) · Zbl 0815.05025
[6] Asratian, A.S.; Khachatrian, N.K., Some localization theorems on Hamiltonian circuits, J. combin. theory B, 49, 287-294, (1990) · Zbl 0708.05038
[7] Benjamini, I.; Schramm, O., Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, Invent. math., 126, 565-587, (1996) · Zbl 0868.31008
[8] Bollobás, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[9] Bruhn, H., The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits, J. combin. theory B, 92, 235-256, (2004) · Zbl 1055.05088
[10] Bruhn, H.; Diestel, R., Maclane’s theorem for arbitrary surfaces, J. combin. theory B, 99, 275-286, (2009) · Zbl 1180.05036
[11] Bruhn, H.; Diestel, R., Duality in infinite graphs, Combin. probab. comput., 15, 75-90, (2006) · Zbl 1082.05028
[12] H. Bruhn, R. Diestel, J. Pott, Dual trees can share their ends (in preparation).
[13] Bruhn, H.; Diestel, R.; Stein, M., Menger’s theorem for infinite graphs with ends, J. graph theory, 50, 199-211, (2005) · Zbl 1077.05053
[14] Bruhn, H.; Kosuch, S.; Win Myint, M., Bicycles and left-right tours in locally finite graphs, European. J. combin., 30, 356-371, (2009) · Zbl 1229.05090
[15] Bruhn, H.; Stein, M., On end degrees and infinite circuits in locally finite graphs, Combinatorica, 27, 269-291, (2007) · Zbl 1136.05030
[16] Bruhn, H.; Stein, M., Maclane’s planarity criterion for locally finite graphs, J. combin. theory B, 96, 225-239, (2006) · Zbl 1088.05026
[17] Bruhn, H.; Yu, X., Hamilton circles in planar locally finite graphs, SIAM J. discrete math., 22, 1381-1392, (2008) · Zbl 1180.05060
[18] Catlin, P.A., Supereulerian graphs: a survey, J. graph theory, 16, 177-196, (1992) · Zbl 0771.05059
[19] Q. Cui, J. Wang, X. Yu, Hamilton circles in infinite planar graphs, J. Combin. Theory B (in press). · Zbl 1193.05117
[20] R. Diestel, Locally finite graphs with ends: a topological approach, 2009, ArXiv:0912.4213.
[21] Diestel, R., Graph theory, (2010), Springer-Verlag, Electronic edition available at: http://diestel-graph-theory.com/ · Zbl 1204.05001
[22] R. Diestel, Locally finite graphs with ends: a topological approach. I. Basic theory, Discrete Math., in press (doi:10.1016/j.disc.2010.05.023).
[23] Diestel, R., End spaces and spanning trees, J. combin. theory B, 96, 846-854, (2006) · Zbl 1107.05028
[24] Diestel, R., The cycle space of an infinite graph, Combin. probab. comput., 14, 59-79, (2005) · Zbl 1067.05037
[25] Diestel, R., The countable erdös – menger conjecture with ends, J. combin. theory B, 87, 145-161, (2003) · Zbl 1021.05063
[26] Diestel, R.; Kühn, D., On infinite cycles I, Combinatorica, 24, 69-89, (2004) · Zbl 1063.05076
[27] Diestel, R.; Kühn, D., Topological paths, cycles and spanning trees in infinite graphs, European. J. combin., 25, 835-862, (2004) · Zbl 1050.05071
[28] Diestel, R.; Kühn, D., A universal planar graph under the minor relation, J. graph theory, 32, 191-206, (1999) · Zbl 0932.05025
[29] Diestel, R.; Leader, I.B., Normal spanning trees, Aronszajn trees and excluded minors, J. lond. math. soc., 63, 16-32, (2001) · Zbl 1012.05051
[30] R. Diestel, P. Sprüssel, The homology of a locally finite graph with ends, Combinatorica (in press).
[31] R. Diestel, P. Sprüssel, Locally finite graphs with ends: a topological approach. III. Fundamental group and homology, Discrete Math. (submitted for publication). · Zbl 1233.05139
[32] Georgakopoulos, A., Connected but not path-connected subspaces of infinite graphs, Combinatorica, 27, 683-698, (2007) · Zbl 1164.05009
[33] Georgakopoulos, A., Infinite Hamilton cycles in squares of locally finite graphs, Adv. math., 220, 670-705, (2009) · Zbl 1205.05133
[34] Georgakopoulos, A., Fleischner’s theorem for infinite graphs, Oberwolfach rep., 4, (2007)
[35] A. Georgakopoulos, Uniqueness of electrical currents in a network of finite total resistance, 2009, preprint arXiv:0906.4080. · Zbl 1209.05116
[36] A. Georgakopoulos, Graph topologies induced by edge lengths, 2009, preprint arXiv:0903.1744. · Zbl 1223.05043
[37] Halin, R., Über die maximalzahl fremder unendlicher wege, Math. nachr., 30, 63-85, (1965) · Zbl 0131.20904
[38] Halin, R., A theorem on \(n\)-connected graphs, J. combin. theory B, 7, 150-154, (1969) · Zbl 0172.25803
[39] Halin, R., Unendliche minimale \(n\)-fach zusammenhängende graphen, Abh. math. sem. univ. Hamburg, 36, 75-88, (1971) · Zbl 0204.57004
[40] Halin, R., Minimization problems for infinite \(n\)-connected graphs, Combin. probab. comput., 2, 417-436, (1993) · Zbl 0793.05086
[41] Halin, R., Miscellaneous problems on infinite graphs, J. graph theory, 35, 128-151, (2000) · Zbl 0960.05001
[42] Lick, D., Critically and minimally \(n\)-connected graphs, (), 199-205 · Zbl 0184.49103
[43] Mader, W., Homomorphieeigenschaften und mittlere kantendichte von graphen, Math. ann., 174, 265-268, (1967) · Zbl 0171.22405
[44] Mader, W., Eine reduktionsmethode für den kantenzusammenhang in graphen, Math. nachr., 93, 187-204, (1979) · Zbl 0434.05048
[45] Mader, W., Paths in graphs reducing the edge-connectivity only by two, Graphs comb., 1, 81-89, (1985) · Zbl 0579.05037
[46] Mader, W., Minimale \(n\)-fach zusammenhängende graphen, Math. ann., 191, 21-28, (1971) · Zbl 0198.29202
[47] Mader, W., Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden graphen, Arch. math., 23, 219-224, (1972) · Zbl 0212.29402
[48] Mader, W., Über minimal \(n\)-fach zusammenhängende, unendliche graphen und ein extremalproblem, Arch. math., 23, 553-560, (1972) · Zbl 0228.05119
[49] Th. Müller, Personal communication, 2007.
[50] Nadler, B., Continuum theory, (1992), Dekker · Zbl 0757.54009
[51] Nash-Williams, C.St.J.A., Edge-disjoint spanning trees of finite graphs, J. lond. math. soc., 36, 445-450, (1961) · Zbl 0102.38805
[52] Nash-Williams, C.St.J.A., Decompositions of finite graphs into forests, J. lond. math. soc., 39, 12, (1964) · Zbl 0119.38805
[53] Oberly, D.J.; Sumner, D.P., Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. graph theory, 3, 351-356, (1979) · Zbl 0424.05036
[54] M. Stein, Extremal infinite graph theory, in this volume.
[55] Stein, M., Forcing highly connected subgraphs in locally finite graphs, J. graph theory, 54, 331-349, (2007) · Zbl 1115.05046
[56] Stein, M., Arboricity and tree-packing in locally finite graphs, J. combin. theory B, 96, 302-312, (2006) · Zbl 1085.05052
[57] Thomassen, C., Nonseparating cycles in \(k\)-connected graphs, J. graph theory, 5, 351-354, (1981) · Zbl 0498.05044
[58] Thomassen, C., Hamiltonian paths in squares of infinite locally finite blocks, Ann. discrete math., 3, 269-277, (1978) · Zbl 0389.05043
[59] Thomassen, C., Reflections on graph theory, J. graph theory, 10, 309-324, (1986) · Zbl 0614.05050
[60] Thomassen, C.; Vella, A., Graph-like continua and menger’s theorem, Combinatorica, 28, (2009)
[61] Tutte, W.T., On the problem of decomposing a graph into \(n\) connected factors, J. lond. math. soc., 36, 221-230, (1961) · Zbl 0096.38001
[62] K. Wagner, Graphentheorie, BI-Hochschultaschenbücher, Bibliographisches Institut, Mannheim, 1970.
[63] Whyburn, G.T., On \(n\)-arc connectedness, Trans. amer. math. soc., 63, 452-456, (1948) · Zbl 0031.41802
[64] Woess, W., Dirichlet problem at infinity for harmonic functions on graphs, (), 189-217 · Zbl 0862.31004
[65] Woess, W., Random walks on infinite graphs and groups, (2000), Cambridge University Press · Zbl 0951.60002
[66] Zhan, S., On Hamiltonian line graphs and connectivity, Discrete math., 89, 89-95, (1991) · Zbl 0727.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.