Properties of almost all graphs and complexes

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u₁, …, u_n, v₁, …, v_n), there exists another vertex w adjacent to each u₁ and not adjacent to any v_i. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.     

Cycle-perfect graphs are perfect

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. © 1996 John Wiley & Sons, Inc.     

Wing-triangulated graphs are perfect

The wing-graph W(G) of a graph G has all edges of G as its vertices; two edges of G are adjacent in W(G) if they are the nonincident edges (called wings) of an induced path on four vertices in G. Hoàng conjectured that if W(G) has no induced cycle of odd length at least five, then G is perfect. As a partial result towards Hoàng's conjecture we prove that if W(G) is triangulated, then G is perfect. © 1997 John Wiley & Sons, Inc.     

Meyniel graphs are strongly perfect

Meyniel (Discrete Math.16 (1976), 339–342) proved that a graph is perfect whenever each of its odd cycles of length at least five has at least two chords. This result is strengthened by proving that every graph satisfying Meyniel's condition is strongly perfect (i.e., each of its induced subgraphs H contains a stable set which meets all the maximal cliques in H).     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

Bull-free Berge graphs are perfect

Abull is the (self-complementary) graph with verticesa, b, c, d, e and edgesab, ac, bc, bd, ce; a graphG is calledBerge if neitherG not its complement contains a chordless cycle whose length is odd and at least five. We prove that bull-free Berge graphs are perfect; a part of our argument relies on a new property of minimal imperfect graphs.This work was done while both authors were at the School of Computer Science, McGill University; support by NSERC is gratefully acknowledged.     

Set intersection representations for almost all graphs

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if θ_k(G) is defined to be the minimum number of labels with which G may be represented using the rule that two vertices are adjacent if and only if they share at least k labels, there exist positive constants c_k and c′_k such that almost every graph G on n vertices satisfies Changing the representation only slightly by defining θ;_odd (G) to be the minimum number of labels with which G can be represented using the rule that two vertices are adjacent if and only if they share an odd number of labels results in quite different behavior. Namely, almost every graph G satisfies Furthermore, the upper bound on θ_odd(G) holds for every graph. © 1996 John Wiley & Sons, Inc.     

Uniquely orderable interval graphs

Interval graphs and interval orders are deeply linked. In fact, edges of an interval graphs represent the incomparability relation of an interval order, and in general, of different interval orders. The question about the conditions under which a given interval graph is associated to a unique interval order (up to duality) arises naturally. Fishburn provided a characterisation for uniquely orderable finite connected interval graphs. We show, by an entirely new proof, that the same characterisation holds also for infinite connected interval graphs. Using tools from reverse mathematics, we explain why the characterisation cannot be lifted from the finite to the infinite by compactness, as it often happens.     

Finite almost simple groups with prime graphs all of whose connected components are cliques

We find finite almost simple groups with prime graphs all of whose connected components are cliques, i.e., complete graphs. The proof is based on the following fact, which was obtained by the authors and is of independent interest: the prime graph of a finite simple nonabelian group contains two nonadjacent odd vertices that do not divide the order of the outer automorphism group of this group.     

The union-closed sets conjecture almost holds for almost all random bipartite graphs

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

Delaunay graphs are almost as good as complete graphs

LetS be any set ofN points in the plane and let DT(S) be the graph of the Delaunay triangulation ofS. For all pointsa andb ofS, letd(a, b) be the Euclidean distance froma tob and let DT(a, b) be the length of the shortest path in DT(S) froma tob. We show that there is a constantc (≤((1+√5)/2) π≈5.08) independent ofS andN such that $$\frac{{DT(a,b)}}{{d(a,b)}}< c.$$      

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

Sphericity exceeds cubicity for almost all complete bipartite graphs

We will prove that sphericity exceeds cubicity for complete bipartite graphs K(m,n) with max (m,n) > n₀, that sph K(n,n) ≥ n, and that as a result of the latter there is a complete bipartite graph with sphericity exceeding cubicity for every value of cubicity at least 6. This answers the question of Fishburn [1].     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

When almost all sets are difference dominated

We investigate the relationship between the sizes of the sum and difference sets attached to a subset of {0,1,…,N}, chosen randomly according to a binomial model with parameter p(N), with N^?1 = o(p(N)). We show that the random subset is almost surely difference dominated, as N → ∞, for any choice of p(N) tending to zero, thus confirming a conjecture of Martin and O'Bryant. The proofs use recent strong concentration results. Furthermore, we exhibit a threshold phenomenon regarding the ratio of the size of the difference to the sumset. If p(N) = o(N^?1/2) then almost all sums and differences in the random subset are almost surely distinct and, in particular, the difference set is almost surely about twice as large as the sumset. If N^?1/2 = o(p(N)) then both the sum and difference sets almost surely have size (2N + 1) ? O(p(N)^?2), and so the ratio in question is almost surely very close to one. If p(N) = c · N^?1/2 then as c increases from zero to infinity (i.e., as the threshold is crossed), the same ratio almost surely decreases continuously from two to one according to an explicitly given function of c. We also extend our results to the comparison of the generalized difference sets attached to an arbitrary pair of binary linear forms. For certain pairs of forms f and g, we show that there in fact exists a sharp threshold at c_f,g · N^?1/2, for some computable constant c_f,g, such that one form almost surely dominates below the threshold and the other almost surely above it. The heart of our approach involves using different tools to obtain strong concentration of the sizes of the sum and difference sets about their mean values, for various ranges of the parameter p. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Some classes of perfectly orderable graphs

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.     

Critical perfect graphs and perfect 3-chromatic graphs

This paper builds on results based on D. R. Fulkerson's antiblocking polyhedra approach to perfect graphs to obtain information about critical perfect graphs and related clique-generated graphs. Then we prove that Berge's Strong Perfect Graph Conjecture is valid for 3-chromatic graphs.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Almost all cubic graphs are Hamiltonian

In a previous article the authors showed that at least 98.4% of large labelled cubic graphs are hamiltonian. In the present article, this is improved to 100% in the limit by asymptotic analysis of the variance of the number of Hamilton cycles with respect to populations of cubic graphs with fixed numbers of short odd cycles.