A303532 a(n) = M(n,2) = number of graphs on n labeled nodes such that each node participates in no more than two maximal cliques.

1, 2, 8, 60, 694, 10790, 210124, 4963734, 139478544, 4585556242, 173882670804

Offset

1,2

Comments

The analogous sequence for numbers of graphs on n labeled nodes such that each node participates in exactly one maximal clique is the Bell numbers: A000110. The sequence for numbers of graphs on n labeled nodes is A006125.

We provide MATLAB code generating for any fixed n a sequence of "M(n,m) = number of graphs on n labeled nodes such that each node participates in no more than m maximal cliques".

For any fixed n we know the range of m: from 1 to ksi(n), such that M(n,ksi(n)) = M(n,ksi(n)+k) = 2^(n(n-1)/2) for any natural k (2^(n(n-1)/2) -- number of graphs on n labeled nodes). And M(n,ksi(n)-k) < M(n,ksi(n)) for any natural k<ksi(n).

(Unlabeled) graphs where each node participates in no more than two maximal cliques are called domino graphs. They can be characterized as (W4,claw,gem)-free graphs [see Kloks et al.]. - Falk Hüffner, Jun 17 2018

Links

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

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties

T. Kloks, D. Kratsch, and H. Müller, Dominoes, Proceedings of the 20th WG, Springer, 1994.

Denis D. Sokolov, MATLAB scripts, 2018.

Denis D. Sokolov, A Shapley Value for TU-Games with Multiple Membership and Externalities, Master's Thesis, 2018.

Crossrefs

Cf. A000110, A006125.

Sequence in context: A303062 A001188 A355100 * A355106 A113145 A293379

Adjacent sequences: A303529 A303530 A303531 * A303533 A303534 A303535

Keyword

hard,more,nonn

Author

Denis D. Sokolov, Apr 25 2018

Extensions

a(9)-a(11) added using tinygraph by Falk Hüffner, Jun 17 2018

Status

approved