A328060 Number of bipartite Laman graphs on n vertices.

1, 1, 0, 0, 0, 1, 1, 5, 19, 123, 871, 8304, 92539, 1210044, 17860267, 293210063, 5277557739, 103177250918, 2174556695546

Offset: 1

Author

Vsevolod Voronov, Oct 03 2019

Keywords

• nonn
• more

Comments

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 first nontrivial bipartite Laman graph is K_{3,3}. An infinite sequence of such graphs can be obtained from K_{3,3} by Henneberg moves of the first type (i.e., adding a vertex and connecting it with two of the existing vertices from the one part).

Links

• L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
• F. Hüffner, tinygraph, software for generating integer sequences based on graph properties.
• Christoph Koutschan, Mathematica program for generating a list of non-isomorphic Laman graphs on n vertices.
• G. Laman, On Graphs and Rigidity of Planar Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331-340.
• Martin Larsson, C program
• A. Nixon and E. Ross, One brick at a time: a survey of inductive constructions in rigidity theory, arXiv:1203.6623 [math.MG], 2012-2013.
• Wikipedia, Laman graph

Crossrefs

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

Programs

Mathematica

Table[Length[
  Select[LamanGraphs[n],
   BipartiteGraphQ[AdjacencyGraph[G2Mat[#]]] &]], {n, 6, 9}] (* using the program by Christoph Koutschan for generating Laman graphs, see A227117 *)

Extensions

a(13)-a(15) added using tinygraph by Falk Hüffner, Oct 20 2019

a(16)-a(17) added by Martin Larsson, Dec 21 2020

a(18)-a(19) from Martin Larsson added by Max Alekseyev, Jan 14 2025