New Classes of Counterexamples to Hendrickson’s Global Rigidity Conjecture

We examine the generic local and global rigidity of various graphs in ℝ ^d . Bruce Hendrickson showed that some necessary conditions for generic global rigidity are (d+1)-connectedness and generic redundant rigidity, and hypothesized that they were sufficient in all dimensions. We analyze two classes of graphs that satisfy Hendrickson’s conditions for generic global rigidity, yet fail to be generically globally rigid. We find a large family of bipartite graphs for d>3, and we define a construction that generates infinitely many graphs in ℝ⁵. Finally, we state some conjectures for further exploration.     

Necessary Conditions for the Global Rigidity of Direction–Length Frameworks

It is an intriguing open problem to give a combinatorial characterisation or polynomial algorithm for determining when a graph is globally rigid in ℝ ^d . This means that any generic realisation is uniquely determined up to congruence when each edge represents a fixed length constraint. Hendrickson gave two natural necessary conditions, one involving connectivity and the other redundant rigidity. In general, these are not sufficient, but they do suffice in two dimensions, as shown by Jackson and Jordán. Our main result is an analogue of the redundant rigidity condition for frameworks that have both direction and length constraints. For any generic globally rigid direction-length framework in ℝ ^d with at least 2 length edges, we show that deleting any length edge results in a rigid framework. It seems harder to obtain a corresponding result when a direction edge is deleted: we can do this in two dimensions, under an additional hypothesis that we believe to be unnecessary. Our proofs use a lemma of independent interest, stating that a certain space parameterising equivalent frameworks is a smooth manifold. We prove this lemma using arguments from differential topology and the Tarski–Seidenberg theorem on semi-algebraic sets.     

Global Rigidity: The Effect of Coning

Recent results have confirmed that the global rigidity of bar-and-joint frameworks on a graph G is a generic property in Euclidean spaces of all dimensions. Although it is not known if there is a deterministic algorithm that runs in polynomial time and space, to decide if a graph is generically globally rigid, there is an algorithm (Gortler et al. in Characterizing generic global rigidity, arXiv:, 2007) running in polynomial time and space that will decide with no false positives and only has false negatives with low probability. When there is a framework that is infinitesimally rigid with a stress matrix of maximal rank, we describe it as a certificate which guarantees that the graph is generically globally rigid, although this framework, itself, may not be globally rigid. We present a set of examples which clarify a number of aspects of global rigidity.     

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     

Weak quasi‐randomness for uniform hypergraphs

We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let K_k be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (K_k,M(k)) has the property that if the number of copies of both K_k and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

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     

Globally Linked Pairs of Vertices in Equivalent Realizations of Graphs

A two-dimensional framework (G,p) is a graph G = (V,E) together with a map p: V → ℝ². We view (G,p) as a straight line realization of G in ℝ². Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if %and for all equivalent frameworks (G,q), the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors [13] by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a byproduct we simplify the proof of a result of Connelly [6] which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu in [3].     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 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     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Closures,cycles, and paths

In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

New Ore‐Type Conditions for H‐Linked Graphs

For a fixed (multi)graph H, a graph G is H‐linked if any injection f: V(H)→V(G) can be extended to an H‐subdivision in G. The notion of an H ‐linked graph encompasses several familiar graph classes, including k‐linked, k‐ordered and k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.