A126122 -id:A126122 - cp's OEIS frontend

A303829 Birooted graphs: number of unlabeled graphs with n nodes rooted at 2 indistinguishable roots.

0, 2, 6, 28, 148, 1144, 13128, 250240, 8295664, 494367376, 53628829952, 10655018252544, 3893626388008448, 2627758027841688960, 3289042848785452985600, 7666804477507744021487616, 33416397343695235205887366144, 273365202164844511328577434284160

Offset: 1

Brendan McKay, May 01 2018

nonn

Cf. A303831 (connected), A303833 (trees), A126122.

a(n) = 2 * A126122(n). - Alois P. Heinz, May 01 2018

A303830 The number of edge-rooted unlabeled connected graphs with n nodes.

Original entry on oeis.org

0, 1, 2, 10, 56, 477, 5879, 117729, 4014125, 242887444, 26562628943, 5300430360196, 1941457570816837, 1311926679135555495, 1643205542452252078848, 3831756372376104769454402, 16704363592309800046798746041, 136665888984665718748205681747780

Offset: 1

R. J. Mathar, May 01 2018

nonn

			a(4)=10: The quadrangle with 1 choice of rooting. The star graph with 1 choice. The triangle with one protruding edge with 3 choices. The quadrangle with a diagonal with 2 choices. The tretrahedron graph with 1 choice. The linear tree with 2 choices (middle or end edge).

Jean-François Alcover, Table of n, a(n) for n = 1..40

Cf. A126122 (not necessarily connected), A000088, A001349.

nmax = 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[GCD[v[[i]], v[[j]]], {i, 2, Length@v}, {j, 1, i - 1}] + Total[Quotient[v, 2]]);
cross[u_, v_] := Sum[ GCD[u[[i]], v[[j]]], {i, 1, Length@u}, {j, 1, Length@v}];
a22[n_] := If[n < 2, 0, s = 0; Do[s += permcount[p]*(2^(edges[p])*(2^cross[{1, 1}, p] + 2^cross[{2}, p])), {p, IntegerPartitions[n - 2]}]; s/(2 (n - 2)!)];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
A[x_] = Sum[a22[n] x^n, {n, 0, nmax}] / Sum[a88[n] x^n, {n, 0, nmax}] + O[x]^nmax;
CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Jul 07 2018, 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)}
cross(u,v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
gs(N,u) = {1+x*Ser(vector(N,n,my(s=0); forpart(p=n, s+=permcount(p)*(2^(edges(p)+cross(u,p)))); s/n!))}
seq(n)={concat([0], Vec((gs(n, [1,1]) + gs(n, [2]))/(2*gs(n, []))))} \\ Andrew Howroyd, May 04 2018

G.f. A(x) satisfies: A(x)*A000088(x) = A126122(x).

A245246 Number of ways to delete an edge (up to the outcome) in the simple unlabeled graphs on n nodes.

Original entry on oeis.org

0, 1, 3, 14, 74, 571, 6558, 125066, 4147388

Offset: 1

Max Alekseyev, Jul 15 2014

Also, the number of distinct pairs (G,H) of simple unlabeled graphs on n nodes, where H can be obtained from G by deletion of a single edge.

For n<6, we have a(n) = A126122(n), since the non-isomorphic edges in a graph on n<6 nodes uniquely define the result of their deletion. However, there is a graph on 6 nodes (see link below) with two non-isomorphic edges, deletion of either of which results in the same graph. Hence, for n>=6, a(n) < A126122(n).

Max Alekseyev, Example of the graph on 6 nodes, where deletion of red or blue edge (which are non-isomorphic) results in the same graph.
Max Alekseyev et al., Removal of non-isomorphic edges results in the same graph, MathOverflow, 2014.

Cf. A000088, A126122

A304071 Number of simple connected graphs with n nodes rooted at one non-edge.

Original entry on oeis.org

0, 0, 1, 6, 42, 402, 5381, 112776, 3935471, 240684836, 26449057257, 5289513580458, 1939502108505917, 1311274498490104492, 1642800188822966309834, 3831285832174735713684706, 16703340559932677463553709189, 136661710199022168890320488632600, 2105815888079982128884579271408161673, 61310553163194788144046000967760340771668

Offset: 1

Brendan McKay, May 05 2018

nonn

			a(3)=1: the non-edge joins the two leaves. a(4)=6: quadrangle: the non-edge is a diagonal; triangle with protruding edge: the non-edge joins the leaf with a node of degree 2; quadrangle with diagonal: the non-edge is the other diagonal; tetrahedron: no contribution; linear chain: the non-edge either joins the two leaves or a leaf with a node at distance 2; star graph: the non-edge joins two leaves.

Jean-François Alcover, Table of n, a(n) for n = 1..40

Cf. A001349 (not rooted), A126122 (not necessarily connected)

A303830 = Import["https://oeis.org/A303830/b303830.txt", "Table"][[All, 2]];
A303831 = Import["https://oeis.org/A303831/b303831.txt", "Table"][[All, 2]];
a[n_] := A303831[[n]] - A303830[[n]];
a /@ Range[1, 40] (* Jean-François Alcover, Sep 21 2019 *)

a(n) + A303830(n) = A303831(n).

A126133 Number of edge-rooted unlabeled graphs with n edges.

Original entry on oeis.org

1, 2, 7, 21, 66, 210, 699, 2387, 8492, 31329, 120034, 477028, 1965016, 8377888, 36923184, 167972182, 787688821, 3802526173, 18873118341, 96195592212, 502953711022, 2694740822749, 14781176429303, 82931707378322

Offset: 1

Vladeta Jovovic, Mar 07 2007

nonn

			a(3)=7: the triangular graph with one edge rooted. The disconnected graph of the connected linear graph with 3 nodes aside the connected graph with 2 nodes, 2 choices for the root. The three disconnected graphs with 3 graphs on 2 nodes, one of the three with the root. The connected star graph with one edge rooted. The connected linear graph with four nodes, 2 choices for the root. - _R. J. Mathar_, May 03 2018

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Max Alekseyev, Table of n, a(n) for n = 1..40

Cf. A000664, A126122, A303832 (connected), A339063, A339064.

\\ See A339063 for G.
seq(n)={my(A=O(x*x^n)); Vec((G(2*n, x+A, [1, 1]) + G(2*n, x+A, [2]))/(2*(1+x)))} \\ Andrew Howroyd, Nov 21 2020

G.f.: f(x)*x/(1 + x) where f(x) is the g.f. of A339064. - Andrew Howroyd, Nov 22 2020

Terms a(10) onward from Max Alekseyev, May 03 2018

A126123 Triangle read by rows: T(n,k) = number of edge-rooted unlabeled graphs having n nodes and k edges, n > 0, 0 < k <= n*(n-1)/2.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 4, 4, 2, 1, 1, 2, 6, 12, 16, 16, 12, 6, 2, 1, 1, 2, 7, 18, 40, 68, 96, 108, 96, 68, 40, 18, 7, 2, 1, 1, 2, 7, 20, 56, 135, 281, 500, 764, 982, 1068, 982, 764, 500, 281, 135, 56, 20, 7, 2, 1, 1, 2, 7, 21, 63, 181, 485, 1159, 2499, 4788, 8074, 11967, 15566

Offset: 1

Vladeta Jovovic, Mar 07 2007

			0;
1;
1,1,1;
1,2,4,4,2,1;
1,2,6,12,16,16,12,6,2,1;
1,2,7,18,40,68,96,108,96,68,40,18,7,2,1;

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Cf. A126122 (row sums).

cp's OEIS Frontend

A303829 Birooted graphs: number of unlabeled graphs with n nodes rooted at 2 indistinguishable roots.

Views

Author

Keywords

Crossrefs

Formula

A303830 The number of edge-rooted unlabeled connected graphs with n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A245246 Number of ways to delete an edge (up to the outcome) in the simple unlabeled graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A304071 Number of simple connected graphs with n nodes rooted at one non-edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A126133 Number of edge-rooted unlabeled graphs with n edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A126123 Triangle read by rows: T(n,k) = number of edge-rooted unlabeled graphs having n nodes and k edges, n > 0, 0 < k <= n*(n-1)/2.

Views

Author

Keywords

Examples

References

Crossrefs