

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 3chromatic 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

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 nonisomorphic Laman graphs on n vertices.
G. Laman, On Graphs and Rigidity of Planar Skeletal Structures, J. Engineering Mathematics, Vol. 4, No. 4, 1970, pp. 331340.
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], 20122013.
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



