A328060 -id:A328060 - cp's OEIS frontend

A227117 Number of minimally rigid graphs in 2D on n vertices.

1, 1, 1, 1, 3, 13, 70, 608, 7222, 110132, 2039273, 44176717, 1092493042, 30322994747, 932701249291

Offset: 1

David S. Newman, Jul 01 2013

All the minimally rigid graphs on n vertices may be made from the minimally rigid graphs on n-1 vertices by use of two types of constructions called the Henneberg constructions. In the first type a new vertex is added to the graph and two new edges are added connecting the new vertex to two vertices which were already part of the graph. In the second type of construction, two vertices,say v_1 and v_2 which are connected by an edge are selected. Another vertex v_3 is selected. The edge between v_1 and v_2 is deleted. A new vertex w is added to the graph, as well as the edges (v_1,w), (v_2,w),and (v_3,w). Each of these two constructions adds one to the number of vertices and two to the number of edges.

It is known from Pollaczek-Geiringer and Laman that minimally rigid graphs in 2D are exactly the (2,3)-tight graphs. A graph G=(V,E) is (2,3)-tight when |E|=2|V|-3 and for every subgraph G'=(V',E') with at least 2 vertices |E'|<=2|V'|-3. - Georg Grasegger, Sep 17 2024

			A single vertex is rigid, as is two vertices joined by an edge, as is a triangle consisting of three vertices joined pairwise by edges.  So a(1)=a(2)=a(3)=1.  Either of the constructions when applied to the triangle will give a graph consisting of two triangles joined along one side.  Another way to picture this is a square together with one of its diagonals.  Applying the two constructions to this graph gives six graphs, but only three distinct graphs up to graph isomorphism.

Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, The number of realizations of a Laman graph, arXiv:1701.05500 [math.AG], 2017-2018.
L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
Christoph Koutschan, Mathematica program
G. Laman, On Graphs and Rigidity of Plane Skeletal Structures, Journal of Engineering Mathematics 4 (1970), 331-340.
Martin Larsson, Nauty Laman plugin
David S. Newman, Mathematica program
H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, Volume 7, Issue 1, 1927, Pages 58-72.
Eric Weisstein's World of Mathematics, Laman Graph
Wikipedia, Laman graph

Cf. A273468, A328060, A328419.

Table[Length[LamanGraphs[n]], {n, 3, 7}]  (* see link, Christoph Koutschan, May 24 2016 *)

gensparseg $n -K2 -u # With Laman plugin; see link.

a(8) corrected and a(9)-a(12) added by Christoph Koutschan, May 24 2016
a(12) corrected and a(13) computed by Jose Capco added by Christoph Koutschan, Nov 21 2018
Name clarified by Nike Dattani, Sep 28 2019
a(14)-a(15) added by Martin Larsson, Dec 21 2020

A328061 Number of 4-chromatic Laman graphs on n vertices.

Original entry on oeis.org

1, 8, 102, 1601, 29811, 636686, 15298955, 407748141, 11932078866

Offset: 7

Vsevolod Voronov, Oct 03 2019

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The simplest example of a 4-chromatic Laman graph is the Moser spindle.

L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
Christoph Koutschan, Mathematica program for generating a list of non-isomorphic Laman graphs on n vertices.
G. Laman, On Graphs and Rigidity of Plane Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340; alternative link.
Martin Larsson, Nauty Laman plugin
A. Nixon, E. Ross, One brick at a time: a survey of inductive constructions in rigidity theory, arXiv:1203.6623 [math.MG], 2012-2013.
Vsevolod Voronov, Anna Neopryatnaya, and Eugene Dergachev, Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres, arXiv:2106.11824 [math.CO], 2021.
Eric Weisstein's World of Mathematics, Moser spindle is a 4-chromatic Laman graph.
Wikipedia, Laman graph

Cf. A227117, A273468, A328060.

Table[Length[
  Select[LamanGraphs[n],
   IGChromaticNumber[AdjacencyGraph[G2Mat[#]]] == 4 &]], {n, 7, 9}]
(*  using the program by Christoph Koutschan for generating Laman graphs, see A227117, and IGraph/M interface by Szabolcs Horvát *)

gensparseg $n -K2 | countg --N # With Laman plugin; see link.

a(13)-a(15) added by Georg Grasegger, Sep 09 2024

A371901 Number of unlabeled Laman graphs on n vertices of degree at most 4.

Original entry on oeis.org

1, 1, 1, 1, 3, 10, 37, 189, 1145, 8089, 64683, 571949, 5499343, 56899844, 628729114, 7380050235

Offset: 1

Max Alekseyev, Apr 11 2024

Martin Larsson, C program
Wikipedia, Laman graph.

Cf. A121941, A227117, A273468, A306420, A328060, A328061.

gensparseg $n -D4 -K2 -u # With Laman plugin; see link.

a(14)-a(16) added by Georg Grasegger, Aug 03 2024

A233288 Number of (3/2,2)-tight graphs with 2n vertices, or kinematic chains with 2n links.

Original entry on oeis.org

1, 1, 2, 16, 230, 6856, 318162, 19819281, 1535380884

Offset: 1

David Eppstein, Dec 06 2013

A 2n-vertex graph is (3/2,2)-sparse if every subgraph with k vertices has at most (3/2)k-2 edges, and (3/2,2)-tight if in addition it has exactly 3n-2 edges; see Lee and Streinu (2008). These graphs represent two-dimensional mechanical systems formed by 2n rigid bodies (links), connected at joints where exactly two links are pinned together and can rotate relative to each other, with the entire system having one degree of freedom and having no rigid subsystems. The vertices of the graph represent links and the edges represent joints.

			For n=1 the single example (a graph with two vertices and one edge) is represented by familiar mechanical systems including door hinges and pairs of scissors. For n=3 the a(3)=2 solutions are the 6-vertex 7-edge graphs Theta(1,3,3) and Theta(2,2,3), each of which has two degree-three vertices connected by three paths of the given lengths. These correspond respectively to the Watt linkage (two four-bar linkages sharing a pair of adjacent links) and the Stephenson linkage.

Eric A. Butcher and Chris Hartman, Efficient enumeration and hierarchical classification of planar simple-jointed kinematic chains: Application to 12- and 14-bar single degree-of-freedom chains, Mechanism and Machine Theory 30 (2005), 1030-1050.
Martin Larsson, Nauty Laman plugin
Audrey Lee and Ileana Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (2008), 1425-1437.
E. E. Peisakh, Structural analysis of planar jointed mechanisms: Current state and problems, J. Machinery Manufacture and Reliability 37 (2008), 207-212.
Rajesh P. Sunkari and Linda C. Schmidt, Structural synthesis of planar kinematic chains by adapting a Mckay-type algorithm, Mechanism and Machine Theory 41 (2006), 1021-1030. This paper sources the 19819281 value for n=8 but contains a typo for n=7.

Cf. A227117, A273468, A306420, A328060, A328061, A371901.

gensparseg 2*$n -K3/2L2 -u # With Laman plugin; see Larsson link.

a(9) from Martin Larsson added by Max Alekseyev, Jan 14 2025

cp's OEIS Frontend

A227117 Number of minimally rigid graphs in 2D on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

nauty

Extensions

A328061 Number of 4-chromatic Laman graphs on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

nauty

Extensions

A371901 Number of unlabeled Laman graphs on n vertices of degree at most 4.

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

A233288 Number of (3/2,2)-tight graphs with 2n vertices, or kinematic chains with 2n links.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Extensions