A053465 -id:A053465 - cp's OEIS frontend

A004102 Number of signed graphs with n nodes. Also number of 2-multigraphs on n nodes.

1, 1, 3, 10, 66, 792, 25506, 2302938, 591901884, 420784762014, 819833163057369, 4382639993148435207, 64588133532185722290294, 2638572375815762804156666529, 300400208094064113266621946833097, 95776892467035669509813163910815022152

Offset: 0

N. J. A. Sloane

A 2-multigraph is similar to an ordinary graph except there are 0, 1 or 2 edges between any two nodes (self-loops are not allowed).

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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 = 0..50 (terms 1..22 from R. W. Robinson)
M. Adamaszek, The smallest nonevasive graph property, Disc. Mathem. Graph Theory 34 (2014) 857
Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.
J. Cummings, D. Kral, F. Pfender, K. Sperfeld et al., Monochromatic triangles in three-coloured graphs, arXiv preprint arXiv:1206.1987 [math.CO]. 2012. - From _N. J. A. Sloane_, Nov 25 2012
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
R. W. Robinson & N. J. A. Sloane, Correspondence, 1970-1980

A column of A063841.

Cf. A053465.

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[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 16, 0] (* Jean-François Alcover, Aug 17 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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Sep 25 2018

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A004102(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

Euler transform of A053465. - Andrew Howroyd, Sep 25 2018

More terms from Vladeta Jovovic, Jan 06 2000

a(0)=1 prepended and a(15) added by Andrew Howroyd, Sep 25 2018

A318590 Number of connected balanced simple signed graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 5, 28, 177, 1982, 33997, 1020516, 54570672, 5347070228, 967135763525, 324200029119318, 202046821340636691, 234878262433630160622, 511060736355598412146405, 2088401066728281847415734793, 16079824271822965645002329491423, 233994776259866281916838227225733732

Offset: 0

Andrew Howroyd, Sep 25 2018

nonn

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

Cf. A005142, A034892, A053465, A054919, A054921.

a(2*n+1) = A054921(2*n+1)/2, a(2*n) = (a(n) + A054919(n) + A054921(2*n) - A054921(n))/2.

Inverse Euler transform of A034892.

A320499 Number of connected self-dual signed graphs with n nodes.

Original entry on oeis.org

1, 1, 0, 1, 3, 14, 62, 572, 7409, 163284, 5736443, 342169618, 33534945769, 5442700283638, 1484664946343496, 664513607618098252, 508538464299389501337, 635542752091150346032474, 1374528064543283977151585962, 4842758246111267151697826493193

Offset: 0

N. J. A. Sloane, Oct 26 2018

nonn

Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273, fourth table.
Andrew Howroyd, PARI Program

Cf. A004102 (signed graphs), A004104 (self-dual), A053465 (connected signed graphs).

\\ See link for program.
A320499seq(20) \\ Andrew Howroyd, Jan 27 2020

a(2*n-1) = b(2*n-1), a(2*n) = b(2*n) - (A053465(n) - a(n))/2 where b is the Inverse Euler transform of A004104. - Andrew Howroyd, Jan 27 2020

Dead sequence restored by Andrew Howroyd, Jan 26 2020

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, Jan 26 2020

A084565 Number of connected switching classes of signed graphs with n nodes.

Original entry on oeis.org

1, 1, 3, 12, 79, 1123, 42065, 4880753, 1674021742, 1612191702946, 4291399235883144, 31570649902282023158, 644451747846907273827686, 36675914469877423648734408329, 5846124500387959287169919356171145

Offset: 1

N. J. A. Sloane, Jul 16 2003

nonn

Also, number of unlabeled connected strength 2 Eulerian graphs with n nodes. - Vladeta Jovovic, Mar 14 2009

Bussemaker, F. C.; Cameron, P. J.; Seidel, J. J.; and Tsaranov, S. V., Tables of signed graphs, Report-WSK 91-01, Eindhoven University of Technology, Department of Mathematics and Computing Science, Eindhoven, 1991, 105 pp. MR: 92g:05001.

F. C. Bussemaker, P. J. Cameron, J. J. Seidel, and S. V. Tsaranov, Tables of signed graphs, Report-WSK 91-01, Eindhoven University of Technology, Department of Mathematics and Computing Science, Eindhoven, 1991, 105 pp. (MR: 92g:05001).

Cf. A007127, A053465.

Edited by N. J. A. Sloane Apr 05 2009 at the suggestion of Vladeta Jovovic

A320488 Inverse Euler transform of A004104.

Original entry on oeis.org

1, 1, 0, 1, 4, 14, 65, 572, 7434, 163284, 5736792, 342169618, 33534958026, 5442700283638, 1484664947481018, 664513607618098252, 508538464299684269212, 635542752091150346032474, 1374528064543284187245552390, 4842758246111267151697826493193, 29772724415959420224886585241636839

Offset: 0

N. J. A. Sloane, Oct 25 2018

nonn

The inverse Euler transform of A004104 does not give the number of connected self-dual signed graphs. The combinatorial interpretation of this sequence is that of either a connected self-dual signed graph or a pair of distinct connected signed graphs which are dual to each other (but not self-dual). - Andrew Howroyd, Jan 26 2020

Andrew Howroyd, Table of n, a(n) for n = 0..50
N. J. A. Sloane, Transforms

Cf. A004102, A004104, A053465, A320499.

Definition edited by Andrew Howroyd, Jan 26 2020

cp's OEIS Frontend

A004102 Number of signed graphs with n nodes. Also number of 2-multigraphs on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A318590 Number of connected balanced simple signed graphs on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A320499 Number of connected self-dual signed graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A084565 Number of connected switching classes of signed graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A320488 Inverse Euler transform of A004104.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions