The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328060 Number of bipartite Laman graphs on n vertices. 2
1, 1, 0, 0, 0, 1, 1, 5, 19, 123, 871, 8304, 92539, 1210044, 17860267, 293210063, 5277557739 (list; graph; refs; listen; history; text; internal format)



All the Laman graphs (in other terms, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. А 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).


Table of n, a(n) for n=1..17.

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




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


Cf. A227117, A273468, A328061.

Sequence in context: A199480 A339079 A209111 * A297389 A228479 A187018

Adjacent sequences:  A328057 A328058 A328059 * A328061 A328062 A328063




Vsevolod Voronov, Oct 03 2019


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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 08:27 EDT 2021. Contains 346464 sequences. (Running on oeis4.)