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.     

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.     

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

Schemes of involving dual variables in inverse barrier functions for problems of linear and convex programming

With any stable map from a 3-manifold to ℝ³, we associate a graph with weights in its vertices and edges. These graphs are A-invariants from a global viewpoint. We study their properties and show that any tree with zero weights in its vertices and aleatory weights in its edges can be the graph of a stable map from S ³ to ℝ³.     

The 2‐dimensional rigidity of certain families of graphs

Laman's characterization of minimally rigid 2‐dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2‐dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d‐regular graph is asymptotically almost surely globally rigid for all d ≥ 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154–166, 2007     

On the elusiveness of Hamiltonian property

1. IntroductionA gash G is an ordered pair of disjoillt sets (V, E) such that E is a subset of the setof unordered pairs of V, where the sets V and E are finite. The set V is cajled the setof venices and E is called the set of edges. They are usually denoted by V(G) and E(C),respectively. An edge (x, y) is said to join the venices x and y, and is sometimes denotedby xo or ear. By our definition, a graph does not colltain any loOP, neither does it colltainmultiple edges.Other terms undef…     

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.     

Rigid pentagons in hypercubes

Two sets of vertices of a hypercubes in ⁿ and ^m are said to be equivalent if there exists a distance preserving linear transformation of one hypercube into the other taking one set to the other. A set of vertices of a hypercube is said to be weakly rigid if up to equivalence it is a unique realization of its distance pattern and it is called rigid if the same holds for any multiple of its distance pattern. A method of describing all rigid and weakly rigid sets of vertices of hypercube of a given size is developed. It is also shown that distance pattern of any rigid set is on the face of convex cone of all distance patterns of sets of vertices in hypercubes.Rigid pentagons (i.e. rigid sets of size 5 in hypercubes) are described. It is shown that there are exactly seven distinct types of rigid pentagons and one type of rigid quadrangle. It is also shown that there is a unique weakly rigid pentagon which is not rigid. An application to the study of all rigid pentagons and quadrangles inL ¹ having integral distance pattern is also given.This work was done during a visit of both the authors to Mehta Research Institute, Allahabad, India.     

The realization graph of a degree sequence with majorization gap 1 is Hamiltonian

It is known that the degree sequences of threshold graphs are characterized by the property that they are not majorized strictly by any degree sequence. Consequently every degree sequence d can be transformed into a threshold sequence by repeated operations consisting of subtracting I from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform d into a threshold sequence is called the majorization gap of d. A realization of a degree sequence d of length n is a graph on the vertices 1, …, n, where the degree of vertex i is d_i. The realization graph %plane1D;4A2;(d) of a degree sequence d has as vertices the realizations of d, and two realizations are neighbors in %plane1D;4A2;(d) if one can be obtained from the other by deleting two existing edges [a, b], [c, d] and adding two new edges [a, d]; [b, c] for some distinct vertices a, b, c, d. It is known that %plane1D;4A2;(d) is connected. We show that if d has a majorization gap of 1, then %plane1D;4A2;(d) is Hamiltonian.     

6p阶可解对称图的分类

设ｘ是简单无向图，Ｇ是Ａｕｔ（Ｘ）的一个于群，Ｘ称为Ｇ－对称的，如果Ｇ在ｘ的１－孤（即两相邻顶点构成的有序偶）集合上的作用是传递的；ｘ称为对称图，如果Ｘ是Ａｕｔ（ｘ）－对称的；ｘ称为可解对称的，如果Ａｕｔ（Ｘ）包含可解子群Ｇ，使Ｘ是Ｇ－对称的．本文给出了具有６Ｐ个顶点的可解对称图的一个分类，这里ｐ≥５是素数．     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

Geometry of Configuration Spaces of Tensegrities

Consider a graph G with n vertices. In this paper we study geometric conditions for an n-tuple of points in ℝ ^d to admit a nonzero self-stress with underlying graph G. We introduce and investigate a natural stratification, depending on G, of the configuration space of all n-tuples in ℝ ^d . In particular we find surgeries on graphs that give relations between different strata. Further we discuss questions related to geometric conditions defining the strata for plane tensegrities. We conclude the paper with particular examples of strata for tensegrities in the plane with a small number of vertices.     

Linkless and Flat Embeddings in 3-Space

We consider piecewise linear embeddings of graphs in 3-space ℝ³. Such an embedding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas (J. Comb. Theory, Ser. B 64:185–227, 1995) showed that a graph has a linkless embedding in ℝ³ if and only if it does not contain as a minor any of seven graphs in Petersen’s family (graphs obtained from K ₆ by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℝ³ if and only if it admits a flat embedding into ℝ³, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D⊆ℝ³ with D∩G=∂D=C. Clearly, every flat embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in ℝ³:     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

Representation of proofs by colored graphs and the hadwiger conjecture

A tinted graph is a graph whose arcs are colored with certain colors. A colored graph is a graph whose vertices are colored with certain colors. If M is the set of tinted (or colored tinted) graphs of order k and G is a tinted (or colored tinted) graph, then we shall say that G is M-regular (or M-regularly colored) if all its subgraphs of order k belong to M. We shall show how, for any formula p of the first-order predicate calculus, to construct a finite set B_p of tinted graphs of order 3 and a finite set C_p of colored tinted graphs of order 2 such that ¦-p if and only if there exists a B_p-regular tinted graph not admitting a C_p-regular coloring. Hadwiger's conjecture (HC) is as follows: If no subgraph of a graph without loops G is contractible to a complete graph of order n, then the vertices of G can be colored in n–1 colors such that neighboring vertices are colored with different colors. We construct a formula X of the first-order predicate calculus such that HC is equivalent with X. Thus, HC reduces to HC₁: if all subgraphs of order 3 of the tinted graph G belong to B_X, then G is C_X-regularly colorable. Here B_X and C_X are specific finite sets of tinted graphs of order 3 and colored tinted graphs of order 2, respectively.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 209–216, 1979.     

Bounded Direction–Length Frameworks

A direction–length framework is a pair (G,p) where G=(V;D,L) is a ‘mixed’ graph whose edges are labelled as ‘direction’ or ‘length’ edges and p is a map from V to ℝ ^d for some d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). Let G ⁺ be obtained from G by adding, for each length edge e of G, a direction edge with the same end vertices as e. We show that (G,p) is bounded if and only if (G ⁺,p) is infinitesimally rigid. This gives a characterization of when (G,p) is bounded in terms of the rank of the rigidity matrix of (G ⁺,p). We use this to characterize when a mixed graph is generically bounded in ℝ ^d . As an application we deduce that if (G,p) is a globally rigid generic framework with at least two length edges and e is a length edge of G then (G∖e,p) is bounded.     

The Number of Embeddings of Minimally Rigid Graphs

Rigid frameworks in some Euclidean space are embedded graphs having a unique local realization (up to Euclidean motions) for the given edge lengths, although globally they may have several. We study the number of distinct planar embeddings of minimally rigid graphs with $n$ vertices. We show that, modulo planar rigid motions, this number is at most ${{2n-4}\choose {n-2}} \approx 4^n$. We also exhibit several families which realize lower bounds of the order of $2^n$, $2.21^n$ and $2.28^n$. For the upper bound we use techniques from complex algebraic geometry, based on the (projective) Cayley--Menger variety ${\it CM}^{2,n}(C)\subset P_{{{n}\choose {2}}-1}(C)$ over the complex numbers $C$. In this context, point configurations are represented by coordinates given by squared distances between all pairs of points. Sectioning the variety with $2n-4$ hyperplanes yields at most $deg({\it CM}^{2,n})$ zero-dimensional components, and one finds this degree to be $D^{2,n}=\frac{1}{2}{{2n-4}\choose {n-2}}$. The lower bounds are related to inductive constructions of minimally rigid graphs via Henneberg sequences. The same approach works in higher dimensions. In particular, we show that it leads to an upper bound of $2 D^{3,n}= {({2^{n-3}}/({n-2}})){{2n-6}\choose{n-3}}$ for the number of spatial embeddings with generic edge lengths of the $1$-skeleton of a simplicial polyhedron, up to rigid motions. Our technique can also be adapted to the non-Euclidean case.     

Extremal Problems on Components and Loops in Graphs

The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G) ≤-4 are shown to be disconnected, and if Ω(G) ≥-2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G) =-2, then certainly the graph should be a tree.Similarly, it is shown that if the realization is a connected graph G and Ω(G) ≥ 0, then certainly the graph should be cyclic. Also, when Ω(G) ≤-4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G) ≥ 0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs.We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.     

Kanten-kritische graphen mit der zusammenhangszahl 2

A set of vertices of a graph G represents G if each edge of G is incident with at least one vertex of . A graph G is said to be edge-critical if the minimal number of vertices necessary to represent G decreases if any edge of G is omitted. Plummer [5] has given a method to construct an infinite family of edge-critical graphs with connectivity number 2. We use this method to construct a more extensive class of edge-critical graphs with connectivity number 2 and show that all edge-critical graphs with this connectivity number (K₂) can be constructed from smaller edge-critical graphs. Finally we give examples of edge-critical graphs not constructable from smaller ones by this method.     

Sources and Sinks in Comparability Graphs

We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.