Infinite families of crossing‐critical graphs with prescribed average degree and crossing number

?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010     

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     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

Nearly light cycles in embedded graphs and crossing‐critical graphs

We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large k‐crossing‐critical graph has crossing number at most 2k + 23. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 151–156, 2006     

Proof of a conjecture on fractional Ramsey numbers

Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function r_f (a₁, a₂, …, a_k) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010     

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005     

Triple Crossing Numbers of Graphs

We introduce the triple crossing number,a variation of the crossing number,of a graph,which is the minimal number of crossing points in all drawings of the graph with only triple crossings.It is defined to be zero for planar graphs,and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings.In this paper,we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

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     

Semi‐transitive graphs

In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi‐transitive and semi‐transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi‐transitive spider‐graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi‐transitive graph (if it has more than one) is a bi‐transitive graph. We show how the alternets can be used to understand the structure of a semi‐transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi‐transitive graphs of degree 4 begun by Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

New families of hypohamiltonian graphs

We construct three new infinite families of hypohamiltonian graphs having respectively 3k+1 vertices (k?3), 3k vertices (k?5) and 5k vertices (k?4); in particular, we exhibit a hypohamiltonian graph of order 19 and a cubic hypohamiltonian graph of order 20, the existence of which was still in doubt. Using these families, we get a lower bound for the number of non-isomorphic hypohamiltonian graphs of order 3k and 5k. We also give an example of an infinite graph G having no two-way infinite hamiltonian path, but in which every vertex-deleted subgraph G - x has such a path.     

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     

Regular 4‐critical graphs of even degree

In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004     

Hajós constructions of critical graphs

For every k ≥ 4 there exists a k‐critical graph that is not Hajós‐k‐constructible through a sequence of k‐critical graphs. This completely answers a question of G. Hajós, which has been answered previously only for k = 8 with an example given by P. Catlin. Also the corresponding problem for Ore's construction has the analogous answer for all k ≥ 4. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 37–5, 1999     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

Thickness‐two graphs part one: New nine‐critical graphs,permuted layer graphs,and Catlin's graphs

The purpose of this article is to offer new insight and tools toward the pursuit of the largest chromatic number in the class of thicknesstwo graphs. At present, the highest chromatic number known for a thickness‐two graph is 9, and there is only one known color‐critical such graph. We introduce 40 small 9‐critical thickness‐two graphs, and then use a newconstruction, the permuted layer graphs, together with a construction of Hajós to create an infinite family of 9‐critical thickness‐two graphs. Finally, a non‐trivial infinite subfamily of Catlin's graphs, with directly computable chromatic numbers, is shown to have thickness two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 198–214, 2008