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

1, 0, 1, 4, 12, 36, 108, 324

Offset

0,4

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.

Appears to be essentially the same as A003946.

Links

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

Gus Wiseman, The a(5) = 36 connected graphs with no crossing or nesting edges.

Gus Wiseman, The a(6) = 108 connected graphs with no crossing or nesting edges.

Example

The a(2) = 1 through a(4) = 36 edge-sets:
  {12}  {12,13}     {12,13,14}
        {12,23}     {12,13,34}
        {13,23}     {12,14,34}
        {12,13,23}  {12,23,24}
                    {12,23,34}
                    {12,24,34}
                    {13,23,34}
                    {14,24,34}
                    {12,13,14,34}
                    {12,13,23,34}
                    {12,14,24,34}
                    {12,23,24,34}

Mathematica

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y||x<z<t<y||z<x<y<t]&]], {n, 0, 5}]

Crossrefs

Covering graphs with no crossing or nesting edges are A326329.

Connected simple graphs are A001349.

The case with only crossing edges forbidden is A007297.

Graphs without crossing or nesting edges are A326244.

Cf. A006125, A054726, A117662, A136653.

Cf. A324169, A326210, A326293, A326340.

Sequence in context: A156945 A006817 A163315 * A334877 A003119 A001394

Adjacent sequences: A326336 A326337 A326338 * A326340 A326341 A326342

Keyword

nonn,more

Author

Gus Wiseman, Jun 29 2019

Status

approved