One‐way infinite 2‐walks in planar graphs

We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path.     

Constructions of infinite graphs with Ramsey property

For every infinite cardinal λ and 2 ≤ n < ω there is a directed graph D of size λ such that D does not contain directed circuits of length ≤n and if its vertices are colored with <λ colors, then there is a monochromatic directed circuit of length n + 1. For every infinite cardinal λ and finite graph X there is a λ-sized graph Y such that if the vertices of Y are colored with <λ colors, then there is a monochromatic induced copy of X. Further, Y does not contain larger cliques or shorter odd circuits than X. The constructions are using variants of Specker-type graphs.     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

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     

Existential closure of block intersection graphs of infinite designs having finite block size and index

In this article we study the n‐existential closure property of the block intersection graphs of infinite t‐(v, k, λ) designs for which the block size k and the index λ are both finite. We show that such block intersection graphs are 2‐e.c. when 2?t?k ? 1. When λ = 1 and 2?t?k, then a necessary and sufficient condition on n for the block intersection graph to be n‐e.c. is that n?min{t, ?(k ? 1)/(t ? 1)? + 1}. If λ?2 then we show that the block intersection graph is not n‐e.c. for any n?min{t + 1, ?k/t? + 1}, and that for 3?n?min{t, ?k/t?} the block intersection graph is potentially but not necessarily n‐e.c. The cases t = 1 and t = k are also discussed. © 2011 Wiley Periodicals, Inc. J Combin Designs 19: 85–94, 2011     

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).     

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     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .     

Large classes of infinite k‐cop‐win graphs

While finite cop‐win finite graphs possess a good structural characterization, none is known for infinite cop‐win graphs. As evidence that such a characterization might not exist, we provide as large as possible classes of infinite graphs with finite cop number. More precisely, for each infinite cardinal κ and each positive integer k, we construct 2^κ non‐isomorphic k‐cop‐win graphs satisfying additional properties such as vertex‐transitivity, or having universal endomorphism monoid and automorphism group. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 334–342, 2010     

First order limits of sparse graphs: Plane trees and path‐width

Ne?et?il and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Two‐connected orientations of Eulerian graphs

A graph G = (V, E) is said to be weakly four‐connected if G is 4‐edge‐connected and G – x is 2‐edge‐connected for every x ∈ V. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of a conjecture of A. Frank . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 230–242, 2006     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

Chromatic‐index‐critical graphs of even order

A k‐critical (multi‐) graph G has maximum degree k, chromatic index χ′(G) = k + 1, and χ′(G − e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k‐critical (multi‐) graphs with certain properties to obtain counterexamples to some well‐known conjectures. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 27–36, 1999     

Spectral characterization of line graphs of starlike trees

Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graph G is said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral with G. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra.