Intersection Theorems for Infinite Families of Convex Sets in Graphs

We prove several Helly-type theorems for infinite families of geodesically convex sets in infinite graphs. That is, we determine the least cardinal n such that any family of (particular) convex sets in some infinite graph has a nonempty intersection whenever each of its subfamilies of cardinality less than n has a nonempty intersection. We obtain some general compactness theorems, and some particular results for pseudo-modular graphs, strongly dismantlable graphs and ball-Helly graphs.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

Chromatically unique graphs

We show that two infinite families of graphs are chromatically unique. The graphs in these families can be obtained from the wheel graphs by deleting some of the spoke edges. Also, we prove that certain related graphs are not chromatically unique.     

Planar and infinite hypohamiltonian and hypotraceable graphs

Chvátal raised the question whether or not planar hypohamiltonian graphs exist and Grünbaum conjectured the nonexistence of such graphs. We shall describe an infinite class of planar hypohamiltonian graphs and infinite classes of planar hypotraceable graphs of connectivity two (resp. three). Infinite hypohamiltonian (resp. htpotraceable) graphs are also described. It is shown how the study of infinite hypotraceable graphs leads to a new infinite family of finite hypotraceable graphs.     

The chromatic number of infinite graphs — A survey

We survey some old and new results on the chromatic number of infinite graphs.     

Crossing numbers of sequences of graphs II: Planar tiles

We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k‐crossing‐critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003     

On Minimal Prime Graphs and Posets

We show that there are four infinite prime graphs such that every infinite prime graph with no infinite clique embeds one of these graphs. We derive a similar result for infinite prime posets with no infinite chain or no infinite antichain.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Harmonic functions on locally finite networks

Are there nonconstant bounded harmonic functions on an infinite locally finite network under natural transition conditions as continuity at the ramification nodes and classical Kirchhoff conditions at all vertices? We present sufficient criteria for such a network to be a Liouville space, while we show that a large class of infinite trees admit infinitely many linearly independent bounded harmonic functions. Finally, we show that the standard unit cube grid graphs and some of Kepler’s plane tiling graphs are Liouville spaces.     

Homomorphisms and amalgamation

We prove that for each finite core graph G, the class of all graphs admitting a homomorphism into G is a pseudo-amalgamation class, in the sense of Fraı̈ssé. This fact gives rise to a countably infinite universal pseudo-homogeneous graph which shares some of the properties of the infinite random graph. Our methods apply simultaneously to G-colourings in several classes of relational structures, such as the classes of directed graphs or hypergraphs.     

The chromatic number and rank of the complements of the Kasami graphs

We determine the rank and chromatic number of the complements of all Kasami graphs, some of which form an infinite family of counterexamples to the now disproven rank-coloring conjecture.     

Sub-semigroups determined by the zero-divisor graph

In this paper we study sub-semigroups of a finite or an infinite zero-divisor semigroup S determined by properties of the zero-divisor graph Γ(S). We use these sub-semigroups to study the correspondence between zero-divisor semigroups and zero-divisor graphs. In particular, we discover a class of sub-semigroups of reduced semigroups and we study properties of sub-semigroups of finite or infinite semilattices with the least element. As an application, we provide a characterization of the graphs which are zero-divisor graphs of Boolean rings. We also study how local property of Γ(S) affects global property of the semigroup S, and we discover some interesting applications. In particular, we find that no finite or infinite two-star graph has a corresponding nil semigroup.     

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.     

Curve graphs and Garside groups

We present a simple construction which associates to every Garside group a metric space, called the additional length graph, on which the group acts. These spaces share important features with curve graphs: they are \(\delta \)-hyperbolic, infinite, and typically locally infinite graphs. We conjecture that, apart from obvious counterexamples, additional length graphs have always infinite diameter. We prove this conjecture for the classical example of braid groups \((B_n,B_n^{+},\varDelta )\); moreover, in this framework, reducible and periodic braids act elliptically, and at least some pseudo-Anosov braids act loxodromically. We conjecture that for \(B_n\), the additional length graph is actually quasi-isometric to the curve graph of the n times punctured disk.     

Koszulity of some path categories

We prove Koszulity of certain linear path categories obtained from connected graphs with some infinite directed walk. These categories can be viewed as locally quadratic dual to preprojective algebras.     

Chirality and principal graph obstructions

Determining which bipartite graphs can be principal graphs of subfactors is an important and difficult question in subfactor theory. Using only planar algebra techniques, we prove a triple point obstruction which generalizes all known initial triple point obstructions to possible principal graphs. We also prove a similar quadruple point obstruction with the same technique. Using our obstructions, we eliminate some infinite families of possible principal graphs with initial triple and quadruple points which were a major hurdle in extending subfactor classification results above index 5.     

Spanning cubic graph designs

Graph designs are natural extensions of BIBDs (balanced incomplete block designs). In this paper we explore spanning cubic graph designs and develop tools for constructing some of them. We show that K₁₆ can be decomposed into each of the 4060 connected cubic graphs of order 16, and into precisely 144 of the 147 disconnected cubic graphs of order 16. We also identify some infinite families of cubic graphs of order 6n+4 that decompose K_6n+4.     

Model-interpretability into trees and applications

It will be shown thatn-separated graphs are model-interpretable into trees, in particular this holds for unary function graphs. Hence metamathematical results for trees carry over to more general graphs. We show that trees are stable in some infinite cardinality, hencen-separated graphs are stable, in particular this holds for unary functions. This generalizes results in [4]. Other examples concern decidability and the finite valency satisfiability property.     

A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions

We show that the result of Watkins (1990) [19] on constructing vertex-transitive non-Cayley graphs from line graphs yields a simple method that produces infinite families of vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. We also prove that the graphs arising this way are hamiltonian provided that their valency is at least six.     

On the Laplacian spectrum of an infinite graph

In this paper, we introduce the notion of Laplacian spectrum of an infinite countable graph in a different way than in the papers by B. Mohar. We prove some basic properties of this type of spectrum. The approach used is in line with our approach to the limiting spectrum of an infinite graph. The technique of the Laplacian spectrum of finite graphs is essential in this approach.