Asymptotic enumeration of strongly connected digraphs by vertices and edges

We derive an asymptotic formula for the number of strongly connected digraphs with n vertices and m arcs (directed edges), valid for m ‐ n →∞ as n →∞ provided m = O(nlog n). This fills the gap between Wright's results which apply to m = n + O (1) , and the long‐known threshold for m, above which a random digraph with n vertices and m arcs is likely to be strongly connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Independence,odd girth,and average degree

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n?m?1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011     

Uniform random colored complexes

We present here random distributions on (D + 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2p. These graphs encode D‐dimensional orientable colored complexes. We investigate the behavior of those graphs as p→∞. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order p, as p→∞.     

Estimates of coefficients of chromatic polynomials and numbers of cliques of (c,n,m)‐graphs

This paper is mainly concerned with classes of simple graphs with exactly c connected components, n vertices and m edges, for fixed c,n,m ∈ ?. We find an optimal lower bound for the ith coefficient of the chromatic polynomial of a graph in such a class and also an optimal upper bound for the number of j‐cliques contained in such a graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 81–94, 2003     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

Bounded transversals in multipartite graphs

Transversals in r‐partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f‐bounded transversal s (or f‐BT), that is, transversals whose connected components have order at most f. In some sense we search for the sparsest f‐BT‐free graphs. We obtain estimates on the smallest maximum degree that 3‐partite and 4‐partite graphs without 2‐BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f‐BT‐free graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001     

Dense graphs with small clique number

We consider the structure of K_r‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r ? 5)n/(2r ? 3) are homomorphic to the join K_{r ? 3}∨H, where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K_r‐free graphs with such a minimum degree have chromatic number at most r +1. We also consider the minimum‐degree thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000     

The number of graphs and a random graph with a given degree sequence

We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d₁,…,d_n). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Tight bounds for the vertices of degree k in minimally k‐connected graphs

For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.     

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011     

Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs

We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

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.     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000