Infinite Hamilton cycles in squares of locally finite graphs

We prove Diestel's conjecture that the square G² of a 2-connected locally finite graph G has a Hamilton circle, a homeomorphic copy of the complex unit circle S¹ in the Freudenthal compactification of G².     

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.     

Reconstruction of locally finite connected graphs with at least three infinite wings

Let G be a locally finite connected graph that can be expressed as the union of a finite subgraph and p disjoint infinite subgraphs, where 3 ≦ p < ∞, but cannot be expressed as the union of a finite subgraph and p + 1 disjoint infinite subgraphs. Then G is reconstructible.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

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.     

Hamilton-laceable bi-powers of locally finite bipartite graphs

In this paper we strengthen a result due to Li by showing that the third bi-power of a locally finite connected bipartite graph that admits a perfect matching is Hamilton-laceable, i.e. any two vertices from different bipartition classes are endpoints of some common Hamilton arc.     

Quasi-kernels and quasi-sinks in infinite graphs

Given a directed graph G=(V,E) an independent set A⊂V is called quasi-kernel (quasi-sink) iff for each point v there is a path of length at most 2 from some point of A to v (from v to some point of A). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph G=(V,E) there is a a partition (V₀,V₁) of the vertex set such that the induced subgraph G[V₀] has a quasi-kernel and the induced subgraph G[V₁] has a quasi-sink.     

Self-adjointness of perturbed bi-Laplacians on infinite graphs

We give a sufficient condition for the essential self-adjointness of a perturbation of the square of the magnetic Laplacian on an infinite weighted graph. The main result is applicable to graphs whose degree function is not necessarily bounded. The result allows perturbations that are not necessarily bounded from below by a constant.     

Unavoidable topological minors of infinite graphs

A graph G is loosely-c-connected, or ?-c-connected, if there exists a number d depending on G such that the deletion of fewer than c vertices from G leaves precisely one infinite component and a graph containing at most d vertices. In this paper, we give the structure of a set of ?-c-connected infinite graphs that form an unavoidable set among the topological minors of ?-c-connected infinite graphs. Corresponding results for minors and parallel minors are also obtained.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Finitely locally finite coverings of Banach spaces

A well-known result due to H. Corson states that, for any covering τ by closed bounded convex subsets of any Banach space X containing an infinite-dimensional reflexive subspace, there exists a compact subset C of X that meets infinitely many members of τ. We strengthen this result proving that, even under the weaker assumption that X contains an infinite-dimensional separable dual space, an (algebraically) finite-dimensional compact set C with that property can always be found.     

The dual Cheeger constant and spectra of infinite graphs

In this article we study the top of the spectrum of the normalized Laplace operator on infinite graphs. We introduce the dual Cheeger constant and show that it controls the top of the spectrum from above and below in a similar way as the Cheeger constant controls the bottom of the spectrum. Moreover, we show that the dual Cheeger constant at infinity can be used to characterize that the essential spectrum of the normalized Laplace operator shrinks to one point.     

Hamiltonian properties of locally connected graphs with bounded vertex degree

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)?4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)?3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33-38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257-260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)?7 is NP-complete.     

On locally finite -groups satisfying an Engel condition

For a given positive integer and a given prime number , let be the integer satisfying . We show that every locally finite -group, satisfying the -Engel identity, is (nilpotent of -bounded class)-by-(finite exponent) where the best upper bound for the exponent is either or if is odd. When the best upper bound is or . In the second part of the paper we focus our attention on -Engel groups. With the aid of the results of the first part we show that every -Engel -group is soluble and the derived length is bounded by some constant.

     

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.     

Classification of connected commutative locally Nash groups

In this article, we classify connected commutative (locally) Nash groups, which is a continuation of our previous work on the classification of abelian Nash manifolds. Our results generalize the classification of the one-dimensional case by Madden-Stanton and the two-dimensional case by Baro-Vicente-Otero. Moreover, we determine the affineness and toroidal affineness of a connected commutative Nash group.