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.     

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.     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

Connected but not path-connected subspaces of infinite graphs

Solving a problem of Diestel [9] relevant to the theory of cycle spaces of infinite graphs, we show that the Freudenthal compactification of a locally finite graph can have connected subsets that are not path-connected. However we prove that connectedness and path-connectedness to coincide for all but a few sets, which have a complicated structure.     

Eulerian edge sets in locally finite graphs

In a finite graph, an edge set Z is an element of the cycle space if and only if every vertex has even degree in Z. We extend this basic result to the topological cycle space, which allows infinite circuits, of locally finite graphs. In order to do so, it becomes necessary to attribute a parity to the ends of the graph.     

The relative degree and large complete minors in infinite graphs

Finite graphs of large minimum degree have large complete (topological) minors. We propose a new and very natural notion, the relative degree of an end, which makes it possible to extend this fact to locally finite graphs and to graphs with countably many ends. We conjecture the extension to be true for all infinite graphs.     

The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits

We extend Tutte's result that in a finite 3-connected graph the cycle space is generated by the peripheral circuits to locally finite graphs. Such a generalization becomes possible by the admission of infinite circuits in the graph compactified by its ends.     

The homology of a locally finite graph with ends

We show that the topological cycle space of a locally finite graph is a canonical quotient of the first singular homology group of its Freudenthal compactification, and we characterize the graphs for which the two coincide. We construct a new singular-type homology for non-compact spaces with ends, which in dimension 1 captures precisely the topological cycle space of graphs but works in any dimension.     

On Infinite Cycles I

We adapt the cycle space of a finite graph to locally finite infinite graphs, using as infinite cycles the homeomorphic images of the unit circle S¹ in the graph compactified by its ends. We prove that this cycle space consists of precisely the sets of edges that meet every finite cut evenly, and that the spanning trees whose fundamental cycles generate this cycle space are precisely the end-faithful spanning trees. We also generalize Eulers theorem by showing that a locally finite connected graph with ends contains a closed topological curve traversing every edge exactly once if and only if its entire edge set lies in this cycle space.To the memory of C. St. J. A. Nash-Williams     

Embedding a graph-like continuum in a surface

Graph-like continua provide a very natural setting for generalizing finite graphs to infinite, compact structures. For example, the Freudenthal compactification of a locally finite graph, exploited by Diestel and his students in their study of the cycle space of an infinite graph, is an example of a graph-like continuum. Generalizing earlier works in special cases, the authors, along with Christian, have proved MacLane’s and Whitney’s characterizations of planarity for graph-like continua (Electron. J. Combin. 17 (2010)). In this work, we consider embeddings of graph-like continua in compact surfaces and show that: (i) every edge is in an open disc that meets the graph-like continuum precisely in that edge; (ii) there are natural analogues of face boundary walks; (iii) there is a graph-like continuum triangulating the same surface and containing as a sub-graphlike continuum the original embedded graph-like continuum; (iv) the face boundaries generate a subspace of the cycle space; and (v) the quotient of the cycle space by the boundary cycles is the homology of the surface. These all generalize results known for embeddings of finite graphs.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

Quasi-isometries between non-locally-finite graphs and structure trees

We prove several criteria for quasi-isometry between non-locally-finite graphs and their structure trees. Results ofMöller in [11] for locally finite and transitive graphs are generalized. We also give a criterion in terms of correspondence between the ends of the graph and the ends of the structure tree.     

A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

Quasi-isometries between graphs and trees

Criteria for quasi-isometry between trees and general graphs as well as for quasi-isometries between metrically almost transitive graphs and trees are found. Thereby we use different concepts of thickness for graphs, ends and end spaces. A metrically almost transitive graph is quasi-isometric to a tree if and only if it has only thin metric ends (in the sense of Definition 3.6). If a graph is quasi-isometric to a tree then there is a one-to-one correspondence between the metric ends and those d-fibers which contain a quasi-geodesic. The graphs considered in this paper are not necessarily locally finite.     

On the homology of locally compact spaces with ends

We propose a homology theory for locally compact spaces with ends in which the ends play a special role. The approach is motivated by results for graphs with ends, where it has been highly successful. But it was unclear how the original graph-theoretical definition could be captured in the usual language for homology theories, so as to make it applicable to more general spaces. In this paper we provide such a general topological framework: we define a homology theory which satisfies the usual axioms, but which maintains the special role for ends that has made this homology work so well for graphs.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

An extension of Sallee’s theorem to infinite locally finite vap-free plane graphs

A graph isk-cyclable if givenk vertices there is a cycle that contains thek vertices. Sallee showed that every finite 3-connected planar graph is 5-cyclable. In this paper, by characterizing the circuit graphs and investigating the structure of LV-graphs, we extend his result to 3-connected infinite locally finite VAP-free plane graphs.     

Bounding the feedback vertex number of digraphs in terms of vertex degrees

The Turán bound (Turán (1941) [17]) is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality (Caro (1979) [4] and Wei (1981) [18]), which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex out-degrees and in terms of average out-degree, respectively.