Graph-like spaces: An introduction

Thomassen and Vella (Graph-like continua, augmenting arcs, and Menger’s Theorem, Combinatorica, doi:10.1007/s00493-008-2342-9) have recently introduced the notion of a graph-like space, simultaneously generalizing infinite graphs and many of the compact spaces recently used by Diestel or Richter (and their coauthors) to study cycle spaces and related problems in infinite graphs. This work is a survey to introduce graph-like spaces and shows how many of these works on compact spaces can be generalized to compact graph-like spaces.     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

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     

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.     

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.     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

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.     

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.     

NOTE The Johnson Graphs Satisfy a Distance Extension Property

G has property if whenever F and H are connected graphs with and |H|=|F|+1, and and are isometric embeddings, then there is an isometric embedding such that . It is easy to construct an infinite graph with for all k, and holds in almost all finite graphs. Prior to this work, it was not known whether there exist any finite graphs with . We show that the Johnson graphs J(n,3) satisfy whenever , and that J(6,3) is the smallest graph satisfying . We also construct finite graphs satisfying and local versions of the extension axioms studied in connection with the Rado universal graph. Received June 9, 1998     

局部大边宽嵌入图的面圈和C-桥的结构

In this paper,we show that for a locally LEW-embedded 3-connected graph G in orientable surface,the following results hold:1) Each of such embeddings is minimum genus embedding;2) The facial cycles are precisely the induced nonseparating cycles which implies the uniqueness of such embeddings;3) Every overlap graph O(G,C) is a bipartite graph and G has only one C-bridge H such that CUH is nonplanar provided C is a contractible cycle shorter than every noncontractible cycle containing an edge of C.This ext...     

On Infinite Cycles II

We adapt the cycle space of a finite or locally finite graph to graphs with vertices of infinite degree, using as cycles the homeomorphic images of the unit circle S¹ in the graph together with its ends. We characterize the spanning trees whose fundamental cycles generate this cycle space, and prove infinite analogues to the standard characterizations of finite cycle spaces in terms of edge-decomposition into single cycles and orthogonality to cuts.To the memory of C. St. J. A. Nash-Williams     

Rectangular and visibility representations of infinite planar graphs

We provide a new method for extending results on finite planar graphs to the infinite case. Thus a result of Ungar on finite graphs has the following extension: Every infinite, planar, cubic, cyclically 4‐edge‐connected graph has a representation in the plane such that every edge is a horizontal or vertical straight line segment, and such that no two edges cross. A result of Tamassia and Tollis extends as follows: Every countably infinite planar graph is a subgraph of a visibility graph. Furthermore, every locally finite, 2‐connected, planar graph is a visibility graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 257–265, 2006     

紧图的两个结果及其应用

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值． 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图． 利用这两个结果,从已知紧图可构造出无穷多个紧图族．     

On the Cycle Space of an Infinite 3-connected Graph

Problems related to Tutte’s theorem on the generation of the cycle space of a 3-connected finite graph are discussed for infinite graphs.     

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.     

Minor‐universal planar graphs without accumulation points

We show that the countably infinite union of infinite grids, H say, is minor‐universal in the class of all graphs that can be drawn in the plane without vertex accumulation points, i.e., that H contains every such graph as a minor. Furthermore, we characterize the graphs that occur as minors of the infinite grid by a natural topological condition on their embeddings. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 1–7, 2001     

On quotient spaces of compact lie groups by Tori centralizers

We consider the graph of the homogeneous space K/L, where K is a compact Lie group and L is the centralizer of a torus in K. We obtain a characterization of those spaces whose graphs admit embeddings in a certain standard graph. We compute the number of arcs in such graphs. We also give a simple expression for the Euler class of the homogeneous space K/L.     

A characterization of projective-planar signed graphs

A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph.     

Continua for which connected partitions are compact

We investigate connected partitions of continua into compacta. In particular, we consider continua with property that every connected partition into compacta is compact. We characterize graphs which have this property as the trees and the simple closed curve. Dendrites are shown to have the property. An example of a nonlocally connected continuum with the property is also given.     

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.