Locally finite graphs with ends: A topological approach, I. Basic theory

This paper is the first 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 [18]. They are complemented by a third part [28], 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. While the second part of this survey [19] will concentrate on those applications, this first part explores the new theory as such: it introduces the basic concepts and facts, describes some of the proof techniques that have emerged over the past 10 years (as well as some of the pitfalls these proofs have in stall for the naive explorer), and establishes connections to neighbouring fields such as algebraic topology and infinite matroids. Numerous open problems are suggested.     

Locally finite graphs with ends: A topological approach, II. Applications

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 [20]. They are complemented by a third part [31], 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.     

局部有限超拓扑的局部紧性

本文讨论了赋予局部有限拓扑的非空闲子集超空间的局部紧性.主要结果是:X正则,则其闭子集超空间局部紧当且仅当X可表示成一个紧空间与一个离散空间的拓扑和.     

The fundamental group of a locally finite graph with ends

We characterize the fundamental group of a locally finite graph G with ends combinatorially, as a group of infinite words. Our characterization gives rise to a canonical embedding of this group in the inverse limit of the free groups π₁(G^′) with G^′⊆G finite.     

Locally Compact Path Spaces

It is shown that the space X^[0,1], of continuous maps [0,1]X with the compact-open topology, is not locally compact for any space X having a nonconstant path of closed points. For a T₁-space X, it follows that X^[0,1] is locally compact if and only if X is locally compact and totally path-disconnected. Mathematics Subject Classifications (2000) 54C35, 54E45, 55P35, 18B30, 18D15.     

On the fastest moving off from a vertex in directed regular graphs

Let Γ be a directed regular locally finite graph, and let $\bar \Gamma $ be the undirected graph obtained by forgetting the orientation of Γ. Let x be a vertex of Γ and let n be a nonnegative integer. We study the length of the shortest directed path in Γ starting at x and ending outside of the ball of radius n centered at x in $\bar \Gamma $ .     

一个Thoms型定理

Thomas［1］ established a genralization of the OrliczPettis theorem as follows: Let Ω be a compact Hausdorff space and X a normed space. If a series ∑fj in C(Ω,X) is subseries convergent in the topology of pointwise convergence on Ω, then ∑fj is also subseries convergent in the topology of uniform convergence on Ω. Note that ∑fj is subseries convergent in the topology of pointwise (resp., uniform) convergence on Ω means that for every (tj)∈{0,1}N, there is an f∈C(Ω,X) such that …     

On compactifications with path connected remainders

We prove that every separable and metrizable space admits a metrizable compactification with a remainder that is both path connected and locally path connected. This result answers a question of P. Simon.

     

The group of isometries of a locally compact metric space with one end

In this note we study the dynamics of the natural evaluation action of the group of isometries G of a locally compact metric space (X,d) with one end. Using the notion of pseudo-components introduced by S. Gao and A.S. Kechris we show that X has only finitely many pseudo-components exactly one of which is not compact and G acts properly on this pseudo-component. The complement of the non-compact component is a compact subset of X and G may fail to act properly on it.     

Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. 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 of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

Analysis of the physical Laplacian and the heat flow on a locally finite graph

We study the physical Laplacian and the corresponding heat flow on an infinite, locally finite graph with possibly unbounded valence.     

The vertex-transitive TLF-planar graphs

We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs. We characterize these graphs by finite combinatorial objects called labeling schemes. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of given degree, as well as most of their transitive groups of automorphisms. In addition,we are able to decide whether a given TLF-planar transitive graph is Cayley or not. This class contains all the one-ended planar Cayley graphs and the normal transitive tilings of the plane.     

Eulerian subgraphs containing given edges

For an integer l0, define to be the family of graphs such that if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in . Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended.