A303532 - OEIS

%I #57 Dec 14 2019 21:25:26

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

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

%C 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.

%C 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".

%C 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).

%C (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

%H F. Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties

%H T. Kloks, D. Kratsch, and H. Müller, <a href="https://pure.tue.nl/ws/files/2013845/9306744.pdf">Dominoes</a>, Proceedings of the 20th WG, Springer, 1994.

%H Denis D. Sokolov, <a href="https://www.dropbox.com/s/0d42ngmoq8lk1w8/M_nl_only.zip?dl=0">MATLAB scripts</a>, 2018.

%H Denis D. Sokolov, <a href="/A303532/a303532_2.pdf">A Shapley Value for TU-Games with Multiple Membership and Externalities</a>, Master's Thesis, 2018.

%Y Cf. A000110, A006125.

%K hard,more,nonn

%O 1,2

%A _Denis D. Sokolov_, Apr 25 2018

%E a(9)-a(11) added using tinygraph by _Falk Hüffner_, Jun 17 2018