A054960 -id:A054960 - cp's OEIS frontend

A000171 Number of self-complementary graphs with n nodes.

1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, 5600, 0, 0, 703760, 11220000, 0, 0, 9168331776, 293293716992, 0, 0, 1601371799340544, 102484848265030656, 0, 0, 3837878966366932639744, 491247277315343649710080, 0, 0

Offset: 1

N. J. A. Sloane

a(n) = A007869(n)-A054960(n), where A007869(n) is number of unlabeled graphs with n nodes and an even number of edges and A054960(n) is number of unlabeled graphs with n nodes and an odd number of edges.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 139, Table 6.1.1.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..100
H. Fripertinger, Self-complementary graphs
Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
Richard A. Gibbs, Self-complementary graphs J. Combinatorial Theory Ser. B 16 (1974), 106--123. MR0347686 (50 #188). - _N. J. A. Sloane_, Mar 27 2012
Sebastian Jeon, Tanya Khovanova, 3-Symmetric Graphs, arXiv:2003.03870 [math.CO], 2020.
B. D. McKay, Self-complementary graphs
R. C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc., 38 (1963), 99-104.
Eric Weisstein's World of Mathematics, Self-Complementary Graph
D. Wille, Enumeration of self-complementary structures, J. Comb. Theory B 25 (1978) 143-150

Cf. A047660, A051251, A047832.

Cf. A008406 (triangle of coefficients of the "graph polynomial").

< -1, {n, 1, 20}]  (* Geoffrey Critzer, Oct 21 2012 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + 2 Total[v];
a[n_] := Module[{s = 0}, Switch[Mod[n, 4], 2|3, 0, _, Do[s += permcount[4 p]*2^edges[p]*If[OddQ[n], n*2^Length[p], 1], {p, IntegerPartitions[ Quotient[n, 4]]}]; s/n!]];
Array[a, 40] (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {4*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + 2*sum(i=1, #v, v[i])}
a(n) = {my(s=0); if(n%4<2, forpart(p=n\4, s+=permcount(4*Vec(p)) * 2^edges(p) * if(n%2, n*2^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 16 2018

a(4n) = A003086(2n).

a(4*n+1) = A047832(n), a(4*n+2) = a(4*n+3) = 0. - Andrew Howroyd, Sep 16 2018

More terms from Ronald C. Read and Vladeta Jovovic

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

Original entry on oeis.org

1, 1, 2, 6, 18, 78, 522, 6178, 137352, 6002584, 509498932, 82545586656, 25251015686776, 14527077828617744, 15713242984902154384, 32000507852263779299344, 122967932076766466347469888, 893788862572805850273939095424, 12318904626562502262191503745716384

Offset: 1

Peter J. Cameron

Andrew Howroyd, Table of n, a(n) for n = 1..50
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.

Cf. A000088, A000171.

Cf. A054960 for graphs with an odd number of edges.

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 *)

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, 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

Average of A000088 and A000171.

More terms from Vladeta Jovovic, Jul 19 2000

Terms a(18) and beyond from Andrew Howroyd, Sep 17 2018

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Original entry on oeis.org

1, 2, 10, 114, 4872, 770832, 441038832, 896679948304, 6513978501814144, 170630215981070456064, 16261454692532635025585792, 5683372715412701087902846672384, 7334542846356464937798016155801130496, 35157828307617499760694672217473135511928832

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A003086, A007869, A054960, A055969.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
b[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
edges4[v_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[2 v[[i]] - 1, {i, 1, Length[v]}];
c[n_] := (s = 0; Do[s += permcount[2 p]*2^edges4[p]*If[OddQ[n], n *4^Length[p], 1], {p, IntegerPartitions[n/2 // Floor]}]; s/n!);
a[n_] := (b[n] + c[n])/2;
Array[a, 14] (* Jean-François Alcover, Aug 26 2019, using Andrew Howroyd's code for b=A000273 and c=A003086 *)

Average of A000273 and A003086.

More terms from Vladeta Jovovic, Jul 19 2000

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Original entry on oeis.org

0, 1, 6, 104, 4736, 770112, 440994608, 896679244544, 6513978322585408, 170630215971902124288, 16261454692523251085611648, 5683372715412699486531047331840, 7334542846356464931239079919515090432, 35157828307617499760690834338506768579289088

Offset: 1

Vladeta Jovovic, Jul 19 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A054928, A007869, A054960.

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003086 = Cases[Import["https://oeis.org/A003086/b003086.txt", "Table"], {, }][[All, 2]];
a[n_] := (A000273[[n + 1]] - A003086[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

a(n) = (A000273(n)-A003086(n))/2.

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A055974 Number of unlabeled digraphs with loops (relations) on n nodes and with an odd number of arcs.

Original entry on oeis.org

0, 1, 4, 52, 1504, 145984, 48461696, 56141454464, 229148544420864, 3333310786076963968, 174695272746603272722432, 33301710992539090379269318144, 23278728241293494481773139193036800, 60084295633556503802059558812644803074048, 576025077880237078776946485247979728479746359296

Offset: 0

Vladeta Jovovic, Jul 19 2000

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000171, A000595, A047832, A054960, A055973.

a(2*n) = (A000595(2*n) - A047832(n))/2; a(2*n+1) = A000595(2*n+1)/2.

a(n) = (A000595(n) - A000171(2*n+1))/2.

a(0)=0 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 19 2020

A137858 Number of unlabeled graphs with n nodes and an even sum of nodes and edges.

Original entry on oeis.org

0, 1, 2, 6, 16, 78, 522, 6178, 137316, 6002584, 509498932, 82545586656, 25251015681176, 14527077828617744, 15713242984902154384, 32000507852263779299344, 122967932076766466336249888

Offset: 1

Tanya Khovanova, Apr 29 2008

nonn

a(n) = A054960(n) for odd n and A007869(n) for even n.

Cf. A054960 Number of unlabeled graphs with n nodes and an odd number of edges. A007869 Complementary pairs of graphs on n nodes. Also unlabeled graphs with n nodes and an even number of edges.

A137861 Number of unlabeled graphs with n nodes and an odd sum of nodes and edges.

Original entry on oeis.org

1, 1, 2, 5, 18, 78, 522, 6168, 137352, 6002584, 509498932, 82545585936, 25251015686776, 14527077828617744, 15713242984902154384, 32000507852263778595584, 122967932076766466347469888

Offset: 1

Tanya Khovanova, Apr 29 2008

nonn

a(n) = A054960(n) for even n and A007869(n) for odd n.

Cf. A054960 Number of unlabeled graphs with n nodes and an odd number of edges. A007869 Complementary pairs of graphs on n nodes. Also unlabeled graphs with n nodes and an even number of edges.

cp's OEIS Frontend

A000171 Number of self-complementary graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055974 Number of unlabeled digraphs with loops (relations) on n nodes and with an odd number of arcs.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A137858 Number of unlabeled graphs with n nodes and an even sum of nodes and edges.

Views

Author

Keywords

Comments

Crossrefs

A137861 Number of unlabeled graphs with n nodes and an odd sum of nodes and edges.

Views

Author

Keywords

Comments

Crossrefs