Characterization of graphs with infinite cyclic edge connectivity

In this paper, we characterize the graphs with infinite cyclic edge connectivity. Then we design an efficient algorithm to determine whether a graph has finite cyclic edge connectivity or infinite cyclic edge connectivity.     

Counterexamples to the edge reconstruction conjecture for infinite graphs

For every infinite cardinal α, there exists a graph with α edges which is not uniquely reconstructible from its family of edge-deleted subgraphs.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Invariant Hamming graphs in infinite quasi-median graphs

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.     

Strongly perfect infinite graphs

An infinite graph G is calledstrongly perfect if each induced subgraph ofG has a coloring (C _i :i ∈I) and a clique meeting each colorC _i . A conjecture of the first author and V. Korman is that a perfect graph with no infinite independent set is strongly perfect. We prove the conjecture for chordal graphs and for their complements. The research was begun at the Sonderforschungsbereich 343 at Bielefeld University and supported by the Fund for the Promotion of Research at the Technion.     

Note on infinite graphs

Some relations between the number of nodes and edges and the degrees of the nodes in infinite graphs are obtained. The structure of infinite connected graphs which have no- ∞ trails is investigated with the help of these. It is shown, for example, that any such graph G has |G| nodes of odd degree.     

Matchings on infinite graphs

Elek and Lippner (Proc. Am. Math. Soc. 138(8), 2939–2947, 2010) showed that the convergence of a sequence of bounded-degree graphs implies the existence of a limit for the proportion of vertices covered by a maximum matching. We provide a characterization of the limiting parameter via a local recursion defined directly on the limit of the graph sequence. Interestingly, the recursion may admit multiple solutions, implying non-trivial long-range dependencies between the covered vertices. We overcome this lack of correlation decay by introducing a perturbative parameter (temperature), which we let progressively go to zero. This allows us to uniquely identify the correct solution. In the important case where the graph limit is a unimodular Galton–Watson tree, the recursion simplifies into a distributional equation that can be solved explicitly, leading to a new asymptotic formula that considerably extends the well-known one by Karp and Sipser for Erd?s-Rényi random graphs.     

Busemann points of infinite graphs

We provide a geometric condition which determines whether or not every point on the metric boundary of a graph with the standard path metric is a Busemann point, that is, it is the limit point of a geodesic ray. We apply this and a related condition to investigate the structure of the metric boundary of Cayley graphs. We show that groups such as the braid group and the discrete Heisenberg group have boundary points of the Cayley graph which are not Busemann points when equipped with their usual generators.

     

The cover-index of infinite graphs

We show that the cover-index of an infinite graph can be expressed in terms of colouring properties of its finite subgraphs when the minimum degree of the graph is finite. We prove that every simple graph with infinite minimum degree contains a tree which is regular of degree and use this to prove that every graph with minimum degree can be decomposed into mutually edge-disjoint spanning subgraphs without ioslated vertices. In particular, the cover-index of a graph equals the minimum degree, when this is infinite.     

Asymptotic connectivity of infinite graphs

We introduce the notion of the asymptotic connectivity of a graph by generalizing to infinite graphs average connectivity as defined by Beineke, Oellermann, and Pippert. Combinatorial and geometric properties of asymptotic connectivity are then explored. In particular, we compute the asymptotic connectivity of a number of planar graphs in order to determine the extent to which this measure correlates with the large-scale geometry of the graph.     

Elusive properties of infinite graphs

A graph property is said to be elusive (or evasive) if every algorithm testing this property by asking questions of the form “is there an edge between vertices $x$ and $y$?” requires, in the worst case, to ask about all pairs of vertices. The unsettled Aanderaa–Karp–Rosenberg conjecture is that every nontrivial monotone graph property is elusive for any finite vertex set. We show that the situation is completely different for infinite vertex sets: the monotone graph properties “every vertex has degree at least $n$” and “every connected component has size at least $m$,” where $n\ge 1$ and $m\ge 2$ are natural numbers, are not elusive for infinite vertex sets, but the monotone graph property “the graph contains a cycle” is elusive for arbitrary vertex set. On the other hand, we also prove that every algorithm testing some natural monotone graph properties, for example, “every vertex has degree at least $n$” or “connected” on the vertex set $\omega$ should check “lots of edges,” more precisely, all the edges of an infinite complete subgraph.     

Water transport on infinite graphs

If the nodes of a graph are considered to be identical barrels – featuring different water levels – and the edges to be (locked) water‐filled pipes in between the barrels, consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, that is, by opening and closing the locks in an elaborate succession. This model is related to an opinion formation process, the so‐called Deffuant model. We consider the initial water profile to be given by i.i.d. unif(0,1) random variables, investigate the supremum of achievable water levels at a given node – or to be more precise, the support of its distribution – and ask in which settings it becomes degenerate, that is, reduces to a single value. This turns out to be the case for all infinite connected quasi‐transitive graphs, with exactly one exception: the two‐sided infinite path.     

Consistency results on infinite graphs

Consistently there exist ℵ₂-chromatic graphs with no ℵ₁-chromatic subgraphs. The statement that every uncountably chromatic graph of size ℵ₁ contains an uncountably chromaticω-connected subgraph is consistent and independent. It is consistent that there is an uncountably chromatic graph of size ℵ_{ω 1} in which every subgraph with size less than ℵ_{ω 1} is countably chromatic. Partially supported by Hungarian Science Research Fund Nu. 1805.     

Hamiltonian paths in infinite graphs

A tight connection is exhibited between infinite paths in recursive trees and Hamiltonian paths in recursive graphs. A corollary is that determining Hamiltonicity in recursive graphs is highly undecidable, viz, Σ ₁ ¹ -complete. This is shown to hold even for highly recursive graphs with degree bounded by 3. Hamiltonicity is thus an example of an interesting graph problem that is outside the arithmetic hierarchy in the infinite case. Parts of this research were carried out during a visit to IBM T.J. Watson Research Center, Hawthorne, NY, in the Summer of 1990. The author holds the William Sussman Professorial Chair in Mathematics.     

A problem concerning infinite graphs

We show that there are graphs G and H which satisfy: (I) for every integer n, H contains n disjoint graphs each isomorphic to G, and (II) H does not contain infinitely many disjoint graphs each isomorphic to G. This answers one of the questions raised by Halin in the Graph Theory Newsletter.