A341941 -id:A341941 - cp's OEIS frontend

A002854 Number of unlabeled Euler graphs with n nodes; number of unlabeled two-graphs with n nodes; number of unlabeled switching classes of graphs with n nodes; number of switching classes of unlabeled signed complete graphs on n nodes; number of Seidel matrices of order n.

1, 1, 2, 3, 7, 16, 54, 243, 2038, 33120, 1182004, 87723296, 12886193064, 3633057074584, 1944000150734320, 1967881448329407496, 3768516017219786199856, 13670271807937483065795200, 94109042015724412679233018144, 1232069666043220685614640133362240

Offset: 1

N. J. A. Sloane

Also called Eulerian graphs of strength 1.
"Switching" a graph at a node complements all the edges incident with that node. The illustration (see link) shows the 3 switching classes on 4 nodes. Switching at any node is the equivalence relation.
"Switching" a signed simple graph at a node negates the signs of all edges incident with that node.
A graph is an Euler graph iff every node has even degree. It need not be connected. (Note that some graph theorists require an Euler graph to be connected so it has an Euler circuit, and call these graphs "even" graphs.)
The objects being counted in this sequence are unlabeled.

			From _Joerg Arndt_, Feb 05 2010: (Start)
The a(4) = 3 Euler graphs on four nodes are:
   1)  o o     2)  o-o     3)  o-o
       o o         |/          | |
                   o o         o-o
(End)

F. Buekenhout, ed., Handbook of Incidence Geometry, 1995, p. 881.
F. C. Bussemaker, R. A. Mathon and J. J. Seidel, Tables of two-graphs, T.H.-Report 79-WSK-05, Technological University Eindhoven, Dept. Mathematics, 1979; also pp. 71-112 of "Combinatorics and Graph Theory (Calcutta, 1980)", Lect. Notes Math. 885, 1981.
CRC Handbook of Combinatorial Designs, 1996, p. 687.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 114, Eq. (4.7.1).
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
J. J. Seidel, A survey of two-graphs, pp. 481-511 of Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Vol. I, Accademia Nazionale dei Lincei, Rome, 1976; also pp. 146-176 in Geometry and Combinatorics: Selected Works of J.J. Seidel, ed. D.G. Corneil and R. Mathon, Academic Press, Boston, 1991..
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).

Max Alekseyev, Table of n, a(n) for n = 1..88 (terms 1..26 from R. W. Robinson).
P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs., 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, arXiv:1403.2155 [math.CO], 2014.
Akihiro Higashitani and Kenta Ueyama, Combinatorial classification of (+/-1)-skew projective spaces, arXiv:2107.12927 [math.RA], 2021.
Akihiro Higashitani and Kenta Ueyama, Combinatorics of graded module categories over skew polynomial algebras at roots of unity, arXiv:2409.10904 [math.RA], 2024. See p. 11.
T. R. Hoffman and J. P. Solazzo, Complex Two-Graphs via Equiangular Tight Frames, arXiv:1408.0334 [math.CO], 2014.
Michael Hofmeister, Counting double covers of graphs, Journal of Graph Theory 12.3 (1988), 437-444. (Beware of a typo!)
V. A. Liskovec, Enumeration of Euler Graphs, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy)
C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. (copy at N. J. A. Sloane's home page)
Brendan D. McKay, Eulerian graphs
R. E. Peile, Letter to N. J. A. Sloane, Feb 1989.
R. C. Read, Letter to N. J. A. Sloane, Nov. 1976.
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)
N. J. A. Sloane, Switching classes of graphs with 4 nodes.
F. Szöllosi and Patric R. J. Östergård, Enumeration of Seidel matrices, arXiv:1703.02943 [math.CO], 2017.
E. Weisstein's World of Mathematics, Eulerian Graph.
T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47-74.

Cf. A000666, A003049, A085618, A085619, A085620, A007127, A133736.
Bisections: A182012, A182055.
Row sums of A341941.

A002854(n)={ /* Robinson's formula, simplified */ local(s=vector(n)); my( S=0, M()=sum( j=2,n, s[j]*sum( i=1,j-1, s[i]*gcd(i,j))) + sum( i=1,n, i*binomial(s[i],2)+(i\2-1)*s[i]) + !!vecextract(s,4^round(n/2)\3), inc()=!forstep(i=n,1,-1,s[i]n, s[i]=n); next(2))); t==n && S+=2^M()/prod(i=1,n,i^s[i]*s[i]!)); S} \\ M. F. Hasler, Apr 09 2012, adapted for current PARI version on Apr 12, 2018

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A002854(n): return int(sum(Fraction(1<>1)-1)*r+(q*r*(r-1)>>1) for q, r in p.items())+any(q&1 for q in p),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 03 2024

a(n) = Sum_{s} 2^M(s)/Product_{i} i^s(i)*s(i)!, where the sum is over n-tuples s in [0..n]^n such that n = Sum i*s(i), M(s) = Sum_{iM. F. Hasler, Apr 15 2012; corrected by Sean A. Irvine, Nov 05 2014

Terms up to a(18) confirmed by Vladeta Jovovic, Apr 18 2000
Name edited (changed "2-graph" to "two-graph" to avoid confusion with other 2-graphs) and comments on Eulerian graphs by Thomas Zaslavsky, Nov 21 2013
Name clarified by Thomas Zaslavsky, Apr 18 2019

A263626 Number of inequivalent self-complementary Seidel matrices of order n.

Original entry on oeis.org

1, 1, 0, 1, 1, 4, 0, 19, 10, 360, 0, 25112, 720, 6975976, 0, 7030565576, 703760, 25473667704064, 0, 333377175390634880, 9168331776, 15881995583375102901824, 0, 2775171714758797872451279104, 1601371799340544, 1790676527377592615808645709379328, 0, 4291738728096066980970104665682237420544, 3837878966366932639744, 38401679870039848205115101680007123726281532416, 0

Offset: 1

N. J. A. Sloane, Oct 24 2015

nonn

From Petros Hadjicostas, Mar 01 2021: (Start)
On p. 9 of their arxiv paper, Greaves et al. (2014-2015) state that "The number of self-complementary Seidel matrices is known explicitly" and refer to Sozański (1980). The authors apparently refer to formula (20) in Theorem 2 (p. 139) in Sozański (1980). (See also p. 218 in  Greaves et al. (2016).)
The so-called "Seidel matrix" of a graph G was apparently introduced by the Dutch mathematician Johan Jacob Seidel (1967, 1968, and with van Lint in 1966). They are not related to the so-called Euler-Seidel (or just Seidel) matrices named after Leonhard Euler and Philipp Ludwig von Seidel.
A Seidel matrix S = S(G) of a simple labeled graph G with vertex set V = {v_1, ..., v_n} is an n x n symmetric matrix with rows and columns corresponding to the n vertices such that S(i,j) is defined in the following way: S(i,j) = 0 iff i = j; S(i,j) = -1 iff vertex v_i is connected to vertex v_j (i <> j), and S(i,j) = 1 iff vertex v_i is not connected to vertex v_j (i <> j). Thus, S(G) = J - I - 2*A(G), where J is an n x n matrix of 1's, I is the n x n identity matrix, and A(G) is the adjancecy matrix of the labeled graph G.
Two Seidel matrices S1 and S2 are said to be equivalent if S1 can be obtained from S2 by a sequence of simultaneous row i to j and column i to j permutations or by a simultaneous multiplication of a row i and a column i by -1.
Thus, Seidel matrices S1 and S2 are equivalent iff there is a symmetric signed permutation matrix P such that S1 = P*S2*P^T.
A Seidel matrix S is called "self-complementary" if S is equivalent to -S. Thus, S is self-complementary iff there is a symmetric signed permutation matrix P such that S = -P*S*P^T. The sequence a(n) counts equivalence classes of self-complementary n x n Seidel matrices.
In terms of a labeled graph G with Seidel matrix S and vertex set V, a simultaneous row i to j and column i to j permutation of S corresponds to exchanging labels between vertices v_i and v_j. On the other hand, a simultaneous multiplication of row i and column i by -1 corresponds to what Mallows and Sloane (1975) call "switching at node" v_i: if A(i) is the set of vertices in V to which v_i is connected and B(i) is the set of vertices in V to which v_i is not connected, "switching at node v_i" means switching the sets A(i) and B(i) (the vertices connected with the vertices non-connected to v_i). Of course, either A(i) or B(i) may be empty.
Mallows and Sloane (1975) proved that the number of equivalence classes of Seidel matrices of order n is equal to the number of unlabeled even graphs (known colloquially as unlabeled "Euler graphs"). See sequence A002854.
The equivalence class of graphs corresponding to a self-complementary Seidel matrix is closed under complementation.
For simplicity, in the examples below that illustrate equivalence classes Seidel matrices, we only include unlabeled graphs on n = 3 or n = 4 nodes rather than labeled ones. (End)

			From _Petros Hadjicostas_, Mar 01 2021: (Start)
For n = 3, we have the following A000088(3) = 4 unlabeled graphs on 3 nodes:
(1) o     (2)  o      (3)  o      (4)  o
              / \         /           / \
  o   o      o   o       o   o       o-- o
Graphs (1) and (2) form one equivalence class and graphs (3) and (4) form another equivalence class (under the Seidel-Mallows-Sloane "switching" equivalence relation). The complement of (1) is (4) and the complement of (2) is (3), so there are no self-complementary classes; i.e., a(3) = 0. (Here, the number of equivalence classes is A002854(3) = 2.)
For n = 4, the A000088(4) = 11 unlabeled graphs are listed in Mallows and Sloane (1975). There are A002854(4) = 3 equivalence classes, only one of which is self-complementary:
(1) o  o   (2) o -- o   (3) o--o   (4) o  o   (5) o--o
    |          |            |          | /|       | /|
    o  o       o    o       o--o       o--o       o--o
Thus, a(4) = 1. (End)

G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, arXiv:1403.2155 [math.CO], 2014-2015.
G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, Journal of Combinatorial Theory, Series A, 138 (2016), 208-235.
C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. (copy at N. J. A. Sloane's home page)
Johan Jacob Seidel, Strongly regular graphs on L2-type and of triangular type, Nederl. Akad. Wet., Proc., Ser. A, 70 (1967), 188-196. (Zentralblatt 161 #20802)
Johan Jacob Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra and its Applications, 1(2) (1968), 281-298. (Zentralblatt 159 #25403)
Tadeusz Sozański, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory 4 (1980), no. 2, 127-144. (Zentralblatt 434 #05059)
Jacobus Hendricus van Lint and Johan Jacob Seidel, Equilateral point sets in elliptic geometryNederl. Akad. Wetensch. Proc. Ser. A, 69 (= Indag. Math., 28) (1966), 335-348. (Zentralblatt 138 #41702)
Wikipedia, Seidel adjacency matrix.

Cf. A000088, A000171, A002854, A085618 (same ?), A341941.

a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
    I1() = sum(i=1, n, p[i]) - if(J() == 0, 0, 1),
    I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i,j))) - J())/2,
    M2() = sum(i=1, n, if(1 == (i%2), p[i], 0))*(abs((p[1]-1)*(p[1]-2)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
    M() = I2() - I1(),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+=if(M2() == 0, 2^M()/prod(i=1, n, i^p[i]*p[i]!), 0)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021

From Petros Hadjicostas, Mar 01 2021: (Start)
a(n) = 0 for 3 == n mod 4 (see the references).
Conjecture (due to Peter Luschny): a(n) = Sum_{k=0}^{n*(n-1)/2} (-1)^k*A341941(n,k) = [o.g.f. of n-th row of A341941](x=-1).
a(n) = Sum_{p in M2(n)} 2^(I2(p) - I1(p))/f(p), where
p = (p[1], ..., p[n]) is a partition of n written in frequency or multiplicity notation with p[i] >= 0 for i = 1..n and Sum_{i=1..n} i*p[i] = n;
M2(n) is the set of all partitions p of n with either (a) p[i] = 0 for all odd i or (b) p[1] = 1 or 2, and p[i] = 0 for i >= 2 with 0 <> (i mod 4);
f(p) = Product_{i=1..n} p[i]!*i^p[i];
J(p) = Sum_{j=1..floor((n-1)/2)} p[2*j+1];
I1(p) = Sum_{i=1..n} p[i] - if(J(p) == 0, 0, 1); and
I2(p) = (Sum_{1 <= i, j <= n} p[i]*p[j]*gcd(i,j) - J(p))/2.
(This is modification of formula (20) in Theorem 2 (p. 139) in Sozański (1980).)
Note that, if we take sum over all partitions of n, rather than just over M2(n), then we get A002854(n).
If, on the other hand, we consider Sum_{p in M1(n)} 2^I2(p)/f(p), where M1(n) is the set of all partitions p of n with p[1] in {0,1} and p[i] = 0 for i >= 2 with 0 <> (i mod 4), then we get A000171(n).
Finally, if we consider Sum_{p} 2^I2(p)/f(p) over all partitions p of n, then we get A000088(n). (End)

Terms a(13) to a(21) copied from Table I (p. 140) in Sozański (1980). - Petros Hadjicostas, Feb 27 2021

Name edited by and terms a(22) to a(31) from Petros Hadjicostas, Mar 01 2021

cp's OEIS Frontend

A002854 Number of unlabeled Euler graphs with n nodes; number of unlabeled two-graphs with n nodes; number of unlabeled switching classes of graphs with n nodes; number of switching classes of unlabeled signed complete graphs on n nodes; number of Seidel matrices of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions