login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A007869
Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.
13
1, 1, 2, 6, 18, 78, 522, 6178, 137352, 6002584, 509498932, 82545586656, 25251015686776, 14527077828617744, 15713242984902154384, 32000507852263779299344, 122967932076766466347469888, 893788862572805850273939095424, 12318904626562502262191503745716384
OFFSET
1,3
LINKS
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Nevena Francetić, Sarada Herke, and Ian M. Wanless, Parity of Sets of Mutually Orthogonal Latin Squares, arXiv:1703.04764 [math.CO], 2017. See Section 4.1.
Tadeusz Sozański, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory 4 (1980), no. 2, 127-144. (Zentralblatt 434 #05059)
Ferenc Szöllosi, The two-distance sets in dimension four, arXiv:1806.07861 [math.MG], 2018. See Table 1.
FORMULA
Average of A000088 and A000171.
MATHEMATICA
Needs["Combinatorica`"]; Table[Total[Table[NumberOfGraphs[n, m], {m, 0, Binomial[n, 2], 2}]], {n, 1, 15}] (* Geoffrey Critzer, Oct 20 2012; modified by Harvey P. Dale, Aug 08 2013 *)
PROG
(PARI) a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i, j))) - J())/2,
M1() = (abs((p[1]-0)*(p[1]-1)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
inc()=!forstep(i=n, 1, -1, p[i]<n\i && p[i]++ && return; p[i]=0), t); until(inc(), t=0; for( i=1, n, if( n < t+=i*p[i], until(i++>n, p[i]=n); next(2))); t==n && S+=(if(M1() == 0, 2^I2()/prod(i=1, n, i^p[i]*p[i]!), 0) + 2^I2()/prod(i=1, n, i^p[i]*p[i]!))/2); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021
CROSSREFS
Cf. A054960 for graphs with an odd number of edges.
Sequence in context: A113844 A266858 A141580 * A263915 A360516 A144557
KEYWORD
nonn,nice
EXTENSIONS
More terms from Vladeta Jovovic, Jul 19 2000
Terms a(18) and beyond from Andrew Howroyd, Sep 17 2018
STATUS
approved