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

 Hints (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)
 OFFSET 1,8 COMMENTS 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). 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 MATHEMATICA Table[Length[   Select[LamanGraphs[n],    BipartiteGraphQ[AdjacencyGraph[G2Mat[#]]] &]], {n, 6, 9}] (* using the program by Christoph Koutschan for generating Laman graphs, see A227117 *) CROSSREFS Cf. A227117, A273468, A328061. Sequence in context: A199480 A339079 A209111 * A297389 A228479 A187018 Adjacent sequences:  A328057 A328058 A328059 * A328061 A328062 A328063 KEYWORD nonn,more AUTHOR Vsevolod Voronov, Oct 03 2019 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 STATUS approved

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.

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