login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000171 Number of self-complementary graphs with n nodes.
(Formerly M0014 N0780)
14
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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.

REFERENCES

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

LINKS

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

FORMULA

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

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

MATHEMATICA

<<Combinatorica`; Table[GraphPolynomial[n, x]/.x -> -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 *)

PROG

(PARI)

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

CROSSREFS

Cf. A047660, A051251, A047832.

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

Sequence in context: A181501 A213704 A278099 * A054922 A289651 A302751

Adjacent sequences:  A000168 A000169 A000170 * A000172 A000173 A000174

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from R. C. Read (rcread(AT)math.uwaterloo.ca) and Vladeta Jovovic

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 28 04:06 EDT 2020. Contains 338048 sequences. (Running on oeis4.)