A326340 Number of maximal simple graphs with vertices {1..n} and no crossing or nesting edges.

1, 1, 1, 1, 4, 9, 19, 42

Offset

0,5

Comments

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Links

Table of n, a(n) for n=0..7.

Gus Wiseman, The a(6) = 19 maximal non-crossing non-nesting graphs.

Mathematica

fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Subsets[Range[n], {2}]], !MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||x<z<t<y]&]]], {n, 0, 5}]

Crossrefs

Covering graphs with no crossing or nesting edges are A326329.

The case with only crossing edges forbidden is A000108 shifted right twice.

Simple graphs without crossing or nesting edges are A326244.

Connected graphs with no crossing or nesting edges are A326339.

Cf. A006125, A007297, A054726, A117662, A136653.

Cf. A324169, A324327, A324328, A326279, A326293.

Sequence in context: A214318 A300438 A034479 * A183304 A359278 A241351

Adjacent sequences: A326337 A326338 A326339 * A326341 A326342 A326343

Keyword

nonn,more

Author

Gus Wiseman, Jun 29 2019

Status

approved