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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A273468 Number of minimally rigid graphs with n vertices constructible by Henneberg type I moves. 5
1, 1, 1, 1, 3, 11, 61, 499, 5500, 75635, 1237670, 23352425, 498028767 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

A graph is called rigid if, when we fix the length of each edge, it has only finitely many embeddings in the plane. A graph is called minimally rigid (or a Laman graph) if there is no edge that can be omitted while keeping the rigidity property. Laman graphs can be constructed by applying successively Henneberg moves (of type I or type II), starting with the graph that consists of two vertices joined by an edge. Here we consider Laman graphs that can be obtained by using only Henneberg type I moves, which means: adding one vertex and joining it with two different existing vertices.

LINKS

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

L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.

Christoph Koutschan, Mathematica program

G. Laman, On Graphs and Rigidity of Plane Skeletal Structures, Journal of Engineering Mathematics 4 (1970), 331-340.

Wikipedia, Laman graph

EXAMPLE

A single vertex is rigid.

The graph consisting of two vertices joined by an edge is rigid.

A triangle is rigid and it is obtained by a single Henneberg type I move.

One more such move yields the only Laman graph with four vertices.

Also all three Laman graphs with five vertices can be constructed with type I moves. Therefore the first five entries of this sequence agree with A227117.

An example of a Laman graph that cannot be constructed using only Henneberg type I moves is the complete bipartite graph K(3,3).

MATHEMATICA

Table[Length[H1LamanGraphs[n]], {n, 3, 7}]  (* see link *)

CROSSREFS

Cf. A227117.

Sequence in context: A095237 A185385 A024528 * A004108 A203007 A296321

Adjacent sequences:  A273465 A273466 A273467 * A273469 A273470 A273471

KEYWORD

nonn,more

AUTHOR

Christoph Koutschan, May 23 2016

EXTENSIONS

a(13) added by Jose Capco, Dec 07 2018

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 3 22:48 EDT 2020. Contains 333207 sequences. (Running on oeis4.)