|
| |
|
|
A328060
|
|
Number of bipartite Laman graphs on n vertices.
|
|
3
|
|
|
|
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 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
|
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.
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,more,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
a(13)-a(15) added using tinygraph by Falk Hüffner, Oct 20 2019
|
|
|
STATUS
|
approved
|
| |
|
|
