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     

Finite Paths are Universal

We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to new on-line dimensions. Mathematics Subject Classifications (2000) 06A06, 06A07, 05E99, 05C99.J. Nešetřil: Supported by a Grant LN00A56 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

A census of semisymmetric cubic graphs on up to 768 vertices

A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K_1,3 as a normal quotient is investigated in detail. Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201) Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506. Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University of Auckland for hospitality during his visit there in 2003.     

Transitive,Locally Finite Median Graphs with Finite Blocks

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. Sandi Klavžar: Supported by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with the Faculty of Mathematics and Natural Sciences, University of Maribor, Slovenia and the Institute of Mathematics, Physics and Mechanics, Ljubljana.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Finiteness Theorems for Graphs and Posets Obtained by Compositions

We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it.In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.     

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     

Finite Paths are Universal

We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions. *Supported by Grants LN00A56 and 1M0021620808 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.     

Two-ended regular median graphs

We show that regular median graphs of linear growth are the Cartesian product of finite hypercubes with the two-way infinite path. Such graphs are Cayley graphs and have only two ends.For cubic median graphs G the condition of linear growth can be weakened to the condition that G has two ends. For higher degree the relaxation to two-ended graphs is not possible, which we demonstrate by an example of a median graph of degree four that has two ends, but nonlinear growth.     

Graphs with the n‐e.c. adjacency property constructed from resolvable designs

Only recently have techniques been introduced that apply design theory to construct graphs with the n‐e.c. adjacency property. We supply a new random construction for generating infinite families of finite regular n‐e.c. graphs derived from certain resolvable Steiner 2‐designs. We supply an extension of our construction to the infinite case, and thereby give a new representation of the infinite random graph. We describe a family of deterministic graphs in infinite affine planes which satisfy the 3‐e.c. property. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 294–306, 2009     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

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.     

A greedy algorithm for finding maximum spanning trees in infinite graphs

In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST.     

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.     

关于交换群上的Cayley有向图的正规性

Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规,我们定出了交换群上的小度数的非正规的Cayley有向图, 并给出了一个猜想．应用这个结果,给出了pn(n≤2)个点上的度数不超过3的有向对称图的分类,这里p是一个奇素数．     

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.     

Spectra of infinite graphs with tails

We compute explicitly (modulo solutions of certain algebraic equations) the spectra of infinite graphs obtained by attaching one or several infinite paths to some vertices of given finite graphs. The main result concerns a canonical form for the adjacency matrix of such infinite graphs, and the algorithm of its calculation. The argument relies upon the spectral theory of eventually free Jacobi matrices. We also study some other couplings of infinite graphs (stars and Bethe–Caley trees).     

Arithmetical Semigroups Related to Trees and Polyhedra,II — Maps on Surfaces

This paper extends recent investigations by Arnold Knopfmacher and John Knopfmacher [10] of asymptotic enumeration questions concerning finite graphs, trees and polyhedra. The present emphasis is on the counting of non‐isomorphic maps of not necessarily connected finite graphs on arbitrary surfaces. A significant aid towards this goal is provided by an extended abstract prime number theorem, based partly on more delicate tools of analysis due to W. K. Hayman [8].