A008406 -id:A008406 - cp's OEIS frontend

A002785 Number of self-complementary oriented graphs with n nodes.

1, 1, 2, 2, 8, 12, 88, 176, 2752, 8784, 279968, 1492288, 95458560, 872687552, 111698291584, 1787154671104, 457509297625088, 13013584213369088, 6662951988432581120, 341143107490935724032, 349330527429800077778944, 32519496073514216703585280

Offset: 1

N. J. A. Sloane

Also, self-converse tournaments. - Brendan McKay, Dec 31 2020

Farrugia's Chapter 8 on enumeration of self-complementary and self-converse graphs and digraphs contains many explicit formulas as well as an in-depth discussion of the literature on this subject. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005

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
Alastair Farrugia, Self-complementary graphs and generalizations: a comprehensive reference, M.Sc. Thesis, University of Malta, August 1999.
M. R. Sridharan, Self-complementary and self-converse oriented graphs , Nederl. Akad. Wetensch. Proc. Ser. A 73=Indag. Math. 32 1970 441-447. [Annotated scanned copy]
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A000171, A003086, A005639.

with(combinat, partition): j:=proc(p) local k, jpart: jpart:=[seq(0,k=1..max(op(p)))]: for k from 1 to nops(p) do jpart[p[k]]:=jpart[p[k]]+1 od: RETURN(jpart): end; numeven:=jtot->2^add(add((2*igcd(r,t)*jtot[r]*jtot[t]),r=1..t-1)+(t*jtot[t]^2-jtot[t]),t=1..nops(jtot)); numodd:=jtot->mul(mul(2^(igcd(r,t)*jtot[r]*jtot[t]),r=1..nops(jtot)),t=1..nops(jtot));den:=jtot->mul(k^jtot[k]*jtot[k]!,k=1..nops(jtot)); testj:=proc(jtot) local i: for i from 1 to floor(nops(jtot)/2) do if(jtot[2*i]<>0) then RETURN(0) fi od: RETURN(1) end; teven:=proc(n) local s,part,k,p,jtot: s:=0: part:=partition(n): for k from 1 to nops(part) do p:=part[k]: jtot:=j(p): if testj(jtot)=1 then s:=s+numeven(jtot)/den(jtot) fi od:RETURN(s): end; todd:=proc(n) local s,part,k,p,jtot: s:=0: part:=partition(n): for k from 1 to nops(part) do p:=part[k]: jtot:=j(p): if testj(jtot)=1 then s:=s+numodd(jtot)/den(jtot) fi od:RETURN(s): end; seq(op([todd(n),teven(n+1)]),n=1..12); (Pab Ter)

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_] := 2*Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}]+Total[v];
oddp[v_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];
a[n_] := Module[{s = 0}, Do[If[oddp[p] == 1, s += permcount[2*p]*2^edges[p]*If[OddQ[n], n*2^Length[p], 1]], {p, IntegerPartitions[Quotient[n, 2]]}]; s/n!];
Array[a, 22] (* Jean-François Alcover, Jan 07 2021, 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) = {2*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
a(n) = {my(s=0); forpart(p=n\2, if(oddp(p), s+=permcount(2*Vec(p)) * 2^edges(p) * if(n%2, n*2^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 16 2018

a(2*n) = Sum_{j partition of n & jk=0 if k even} [ Product_{k} 2^(k*jk^2-jk) * Product_{r

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005

a(1)-a(2) prepended by Andrew Howroyd, Sep 16 2018

A048179 Number of graphs with n nodes and n+1 edges.

Original entry on oeis.org

1, 6, 24, 97, 402, 1637, 6759, 28259, 119890, 517121, 2271860, 10176660, 46541024, 217511951, 1039651295, 5084972068, 25458149446, 130480742790, 684550272269, 3675258986639, 20184618368312, 113340974676578, 650343587802644

Offset: 4

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.

Andrew Howroyd, Table of n, a(n) for n = 4..50 (terms 4..37 from Sean A. Irvine)
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

Cf. A008406.

a(n) = polcoef(G(n, O(x^(n+2))), n+1) \\ G defined in A008406. - Andrew Howroyd, Jan 09 2024

a(n) = A008406(n, n+1). - Andrew Howroyd, Jan 09 2024

More terms from Vladeta Jovovic, Jan 07 2000

More terms from Sean A. Irvine, Jun 06 2017

A048180 Number of graphs with n nodes and n+2 edges.

Original entry on oeis.org

1, 4, 24, 131, 663, 3252, 15772, 75415, 359307, 1711908, 8191607, 39500169, 192525021, 950868860, 4769060224, 24331970791, 126457607026, 670143402073, 3623530476832, 19998343352758, 112668088476243, 647904733883526

Offset: 4

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.

Sean A. Irvine, Table of n, a(n) for n = 4..36
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

Cf. A008406.

More terms from Vladeta Jovovic, Jan 03 2000

More terms from Sean A. Irvine, Jun 07 2017

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 5, 3, 1, 1, 0, 0, 1, 10, 7, 3, 1, 1, 0, 0, 1, 17, 17, 7, 3, 1, 1, 0, 0, 1, 36, 38, 19, 7, 3, 1, 1, 0, 0, 1, 65, 93, 45, 19, 7, 3, 1, 1, 0, 0, 1, 134, 220, 118, 47, 19, 7, 3, 1, 1, 0, 0, 1, 264, 537, 296, 125, 47, 19, 7, 3, 1, 1

Offset: 1

Emeric Deutsch, Mar 05 2014

Sum of entries in row n is A000055(n) (= number of trees with n vertices).
The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196046, from these Matula numbers one obtains the maximum vertex degrees: 2, 3, 3, 3, 4, 4, 3, 5, 3, 4, 6; the frequencies of 2,3,4,5,6 are 1, 5, 3, 1, 1, respectively. See the Maple program.
This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - Andrew Howroyd, Dec 17 2020

			Row n=4 is T(4,2)=1,T(4,3)=1; indeed, the maximum vertex degree in the path P[4] is 2, while in the star S[4] it is 3.
Triangle starts:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1,  1;
  0, 0, 1,  1,  1;
  0, 0, 1,  3,  1, 1;
  0, 0, 1,  5,  3, 1, 1;
  0, 0, 1, 10,  7, 3, 1, 1;
  0, 0, 1, 17, 17, 7, 3, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A000055.

Cf. A144528, A196046, A235111, A332760 (connected graphs), A339788 (forests).

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then max(a(pi(n)), 1+bigomega(pi(n))) else max(a(r(n)), a(s(n)), bigomega(r(n))+bigomega(s(n))) end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 2 .. 6);

\\ Here V(n, k) gives column k of A144528.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, V(n,k-1)[2..1+n]~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - Andrew Howroyd, Dec 17 2020

Columns k=0..1 inserted by Andrew Howroyd, Dec 18 2020

A001430 Number of graphs with n nodes and n-2 edges.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 21, 56, 148, 428, 1305, 4191, 14140, 50159, 185987, 720298, 2905512, 12180208, 52951701, 238253067, 1107432714, 5308573473, 26202267612, 132977762151, 692996060768

Offset: 1

N. J. A. Sloane

			There are 4 graphs with 5 nodes and 3 edges.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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).

Sean A. Irvine, Table of n, a(n) for n = 1..40
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

Cf. A008406, where this is a diagonal.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n-2], {n, 2, 25}] (* Robert G. Wilson v *)

More terms from Vladeta Jovovic, Jan 13 2000

A051337 Number of strongly connected tournaments on n nodes.

Original entry on oeis.org

1, 1, 0, 1, 1, 6, 35, 353, 6008, 178133, 9355949, 884464590, 152310149735, 48234782263293, 28304491788158056, 30964247546702883729, 63468402142317299907481, 244785748571033855024746438, 1782909084196274276970660380187, 24602074618353524534591008760307017

Offset: 0

Vladeta Jovovic

A tournament is strongly connected (or strong) if there is a directed path between any pair of points.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 127, Eq. (5.2.4);
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 523.

Andrew Howroyd, Table of n, a(n) for n = 0..50
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Raphael Yuster, Vector clique decompositions, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), 1221-1238.

Cf. A000568, A054946.

m = 20;
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]}];
oddp[v_] := (For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1);
b[n_] := b[n] = (s = 0; Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; s/n!);
B[x_] = Sum[b[k] x^k, {k, 0, m}];
A[x_] = 2 - 1/B[x];
A[x] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A000568 *)

G.f.: = 2 - 1/B(x) where B(x) = g.f. for A000568.

a(0)=1 prepended and a(18)-a(19) from Andrew Howroyd, Sep 10 2018

A076263 Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 5, 4, 2, 1, 1, 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1, 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 23, 89, 236, 486, 814, 1169, 1454, 1579, 1515, 1290, 970, 658, 400, 220, 114, 56, 24, 11, 5, 2, 1, 1, 47, 240, 797, 2075, 4495

Offset: 1

Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

The index of the T(n,k) in the sequence is ((n-2)^3 - n + 6*k + 8)/6.

T(n,k)=1 for k = n*(n-1)/2-1 and k = n*(n-1)/2 (therefore {1,1} separates sublists for given numbers of vertices (n > 2)).

			There are 2 connected graphs with 4 vertices and 3 edges up to isomorphy (first graph: ((1,2),(2,3),(3,4)); second graph: ((1,2),(1,3),(1,4))). Index within the sequence is ((4-2)^3 - 4 + 6*3 + 8)/6 = 5.
Triangle begins:
   1;
   1;
   1,  1;
   2,  2,  1,   1;
   3,  5,  5,   4,   2,   1,   1;
   6, 13, 19,  22,  20,  14,   9,  5,  2,  1,  1;
  11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1;

T. D. Noe, Rows 1 to 16 of triangle, flattened (from Gordon Royle's website)
Keith M. Briggs, Combinatorial Graph Theory.
Sriram V. Pemmaraju, The Combinatorica Project
Marko R. Riedel, Number of distinct connected digraphs, Math StackExchange.
Marko Riedel, Maple code for sequences A008406 and A076263 including cycle indices.
Eric Weisstein's World of Mathematics, Connected Graph.

Row lengths (excluding first row): A000124. Number of connected graphs for given number of vertices: A001349. Number of connected graphs for given number of edges: A002905.
Number of entries in the n-th row is A152947. Row sums give A001349.
Starting each row from k=0 gives A054924, which is the main entry for this triangle.

NumberOfConnectedGraphs[vertices_, edges_] := Plus @@ ConnectedQ /@ ListGraphs[vertices, edges] /. {True->1, False ->0}
(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Table[Plus @@ ConnectedQ /@ ListGraphs[Vert, i] /. {True -> 1, False -> 0}, {Vert, 8}, {i, Vert - 1, Vert*(Vert - 1)/2}]

Corrected by Keith Briggs and Robert G. Wilson v, May 01 2005
Rows 5, 6 & 7 from Robert G. Wilson v, Jun 21 2005
More terms from Keith Briggs, Jun 28 2005
Name corrected by Andrey Zabolotskiy, Nov 20 2017

Previous Showing 51-60 of 83 results. Next

cp's OEIS Frontend

A046751 Triangle read by rows of number of connected graphs with n nodes and k edges (n >= 2, 1 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A123551 Triangle read by rows: T(n,k) gives number of unlabeled graphs without endpoints on n nodes and k edges, (n >= 0, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A370315 Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A002785 Number of self-complementary oriented graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A048179 Number of graphs with n nodes and n+1 edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A048180 Number of graphs with n nodes and n+2 edges.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A001430 Number of graphs with n nodes and n-2 edges.

Views

Author