[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a327079 -id:a327079
Displaying 1-10 of 14 results found. page 1 2
     Sort: relevance | references | number | modified | created      Format: long | short | data
A095983 Number of 2-edge-connected labeled graphs on n nodes. +10
38
0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,5
COMMENTS
From Falk Hüffner, Jun 28 2018: (Start)
Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).
Labeled version of A007146. (End)
The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019
LINKS
Jinyuan Wang, Table of n, a(n) for n = 0..82
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.
Gus Wiseman, The a(4) = 10 labeled graphs with spanning edge-connectivity >= 2.
Gus Wiseman, Non-isomorphic representatives of the a(5) = 253 graphs with spanning edge-connectivity >= 2.
FORMULA
a(n) = A001187(n) - A327071(n). - Gus Wiseman, Sep 20 2019
MATHEMATICA
seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
seq[16] (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_, eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds], Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], spanEdgeConn[Range[n], #]>=2&]], {n, 0, 5}] (* Gus Wiseman, Sep 20 2019 *)
PROG
(PARI) \\ here p is initially A053549, q is A198046 as e.g.f.s.
seq(n)={my(v=vector(n));
my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));
my(q=x*exp(p)); p-=q;
for(k=3, n, my(c=polcoeff(p, k)); v[k]=c*(k-1)!; p-=c*q^k);
concat([0], v)} \\ Andrew Howroyd, Jun 18 2018
(PARI) seq(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))/x-1), -(n+1))} \\ Andrew Howroyd, Dec 28 2020
CROSSREFS
Cf. A053549, A198046.
The unlabeled version is A007146.
Row sums of A327069 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with spanning edge-connectivity 2 are A327146.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Graphs without endpoints are A059167.
Graphs with spanning edge-connectivity 1 are A327071.
Cf. A001187, A002218, A052446, A059166, A100743, A322395, A327079, A327144.
KEYWORD
nonn
AUTHOR
Yifei Chen (yifei(AT)mit.edu), Jul 17 2004
EXTENSIONS
Name corrected and more terms from Pavel Irzhavski, Nov 01 2014
Offset corrected by Falk Hüffner, Jun 17 2018
a(12)-a(16) from Andrew Howroyd, Jun 18 2018
STATUS
approved
A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1. +10
27
0, 0, 1, 3, 28, 475, 14736, 818643, 82367552, 15278576679, 5316021393280, 3519977478407687, 4487518206535452672, 11116767463976825779115, 53887635281876408097483776, 513758302006787897939587736715, 9668884580476067306398361085853696 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).
The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty graph.
LINKS
Jean-François Alcover and Vaclav Kotesovec, Table of n, a(n) for n = 0..82 [using A001187 and b-file from A095983]
Eric Weisstein's World of Mathematics, Bridged Graph
FORMULA
a(1) = 0; a(n > 1) = A001187(n) - A095983(n).
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_, eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds], Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], spanEdgeConn[Range[n], #]==1&]], {n, 0, 4}]
CROSSREFS
Column k = 1 of A327069.
The unlabeled version is A052446.
Connected graphs without bridges are A007146.
The enumeration of labeled connected graphs by number of bridges is A327072.
Connected graphs with exactly one bridge are A327073.
Graphs with non-spanning edge-connectivity 1 are A327079.
BII-numbers of set-systems with spanning edge-connectivity 1 are A327111.
Covering set-systems with spanning edge-connectivity 1 are A327145.
Graphs with spanning edge-connectivity 2 are A327146.
Cf. A001187, A001349, A006125, A059166, A322395, A327071, A327077, A327099, A327144.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 24 2019
STATUS
approved
A245797 The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1. +10
22
0, 1, 6, 49, 710, 19011, 954184, 90154415, 16108626420, 5481798833245, 3582369649269620, 4532127781040045649, 11177949079089720090800, 54050029251399545975868271, 514598463471970554205910304780, 9677402372862708729859372687791391 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..50
FORMULA
a(n) = 2^(n*(n+1)/2) - A059167(n).
Binomial transform of A327227 (assuming a(0) = 0).
MATHEMATICA
m = 16;
egf = Exp[x^2/2]*Sum[2^Binomial[n, 2]*(x/Exp[x])^n/n!, {n, 0, m}];
A059167[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
a[n_] := 2^(n(n-1)/2) - A059167[n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Min@@Length/@Split[Sort[Join@@#]]==1&]], {n, 0, 5}] (* Gus Wiseman, Sep 11 2019 *)
CROSSREFS
Equal to row sums of A245796.
The covering case is A327227.
The connected case is A327362.
The generalization to set-systems is A327228.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327229, A327230.
KEYWORD
nonn
AUTHOR
Chai Wah Wu, Aug 01 2014
EXTENSIONS
a(9)-a(16) from Andrew Howroyd, Oct 26 2017
STATUS
approved
A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf. +10
22
0, 0, 1, 3, 31, 515, 15381, 834491, 83016613, 15330074139, 5324658838645, 3522941267488973, 4489497643961740521, 11119309286377621015089, 53893949089393110881259181, 513788884660608277842596504415, 9669175277199248753133328740702449 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Covering means there are no isolated vertices.
A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also graphs with minimum vertex-degree 1.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..50
FORMULA
Inverse binomial transform of A245797, if we assume A245797(0) = 0.
EXAMPLE
The a(4) = 31 edge-sets:
{12,34} {12,13,14} {12,13,14,23}
{13,24} {12,13,24} {12,13,14,24}
{14,23} {12,13,34} {12,13,14,34}
{12,14,23} {12,13,23,24}
{12,14,34} {12,13,23,34}
{12,23,24} {12,14,23,24}
{12,23,34} {12,14,24,34}
{12,24,34} {12,23,24,34}
{13,14,23} {13,14,23,34}
{13,14,24} {13,14,24,34}
{13,23,24} {13,23,24,34}
{13,23,34} {14,23,24,34}
{13,24,34}
{14,23,24}
{14,23,34}
{14,24,34}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]], {n, 0, 5}]
CROSSREFS
Column k=1 of A327366.
The non-covering version is A245797.
The unlabeled version is A324693.
The generalization to set-systems is A327229.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327228, A327230.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 01 2019
STATUS
approved
A327148 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of labeled simple graphs with n vertices and non-spanning edge-connectivity k. +10
17
1, 1, 1, 1, 1, 3, 3, 1, 4, 18, 27, 14, 1, 56, 250, 402, 240, 65, 10, 1, 1031, 5475, 11277, 9620, 4282, 921, 146, 15, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,6
COMMENTS
The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any isolated vertices) to obtain a disconnected or empty graph.
LINKS
Table of n, a(n) for n=0..28.
FORMULA
T(n,k) = Sum_{m = 0..n} binomial(n,m) A327149(m,k). In words, column k is the binomial transform of column k of A327149.
EXAMPLE
Triangle begins:
1
1
1 1
1 3 3 1
4 18 27 14 1
56 250 402 240 65 10 1
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
edgeConnSys[sys_]:=If[Length[csm[sys]]!=1, 0, Length[sys]-Max@@Length/@Select[Union[Subsets[sys]], Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], edgeConnSys[#]==k&]], {n, 0, 4}, {k, 0, Binomial[n, 2]}]//.{foe___, 0}:>{foe}
CROSSREFS
Row sums are A006125.
Column k = 0 is A327199.
Column k = 1 is A327231.
The corresponding triangle for vertex-connectivity is A327125.
The corresponding triangle for spanning edge-connectivity is A327069.
The covering version is A327149.
The unlabeled version is A327236, with covering version A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327079, A327097, A327099, A327102, A327126, A327144, A327196, A327200, A327201.
KEYWORD
nonn,tabf,more
AUTHOR
Gus Wiseman, Aug 27 2019
EXTENSIONS
a(20)-a(28) from Robert Price, May 25 2021
STATUS
approved
A100743 Number of labeled n-vertex graphs without vertices of degree <=1. +10
14
1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,5
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..50
FORMULA
E.g.f.: exp(-x+x^2/2)*(Sum_{n>=0} 2^(n*(n-1)/2)*(x/exp(x))^n/n!). - Vladeta Jovovic, Jan 26 2006
Exponential transform of A059166. - Gus Wiseman, Aug 18 2019
Inverse binomial transform of A059167. - Gus Wiseman, Sep 02 2019
EXAMPLE
From Gus Wiseman, Aug 18 2019: (Start)
The a(4) = 10 edge-sets:
{12,13,24,34}
{12,14,23,34}
{13,14,23,24}
{12,13,14,23,24}
{12,13,14,23,34}
{12,13,14,24,34}
{12,13,23,24,34}
{12,14,23,24,34}
{13,14,23,24,34}
{12,13,14,23,24,34}
(End)
MATHEMATICA
m = 13;
egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];
s = egf + O[x]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]], {n, 0, 4}] (* Gus Wiseman, Aug 18 2019 *)
PROG
(PARI) seq(n)={Vec(serlaplace(exp(-x + x^2/2 + O(x*x^n))*sum(k=0, n, 2^(k*(k-1)/2)*(x/exp(x + O(x^n)))^k/k!)))} \\ Andrew Howroyd, Sep 04 2019
CROSSREFS
Graphs without isolated nodes are A006129.
The connected case is A059166.
Graphs without endpoints are A059167.
Labeled graphs with endpoints are A245797.
The unlabeled version is A261919.
Cf. A095983, A136284, A322395, A327079, A327107, A327227, A327229, A327230.
Cf. A095983, A322395.
KEYWORD
nonn
AUTHOR
Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 03 2005
EXTENSIONS
Terms a(14) and beyond from Andrew Howroyd, Sep 04 2019
STATUS
approved
A327229 Number of set-systems covering n vertices with at least one endpoint/leaf. +10
13
0, 1, 4, 50, 3069, 2521782, 412169726428, 4132070622008664529903, 174224571863520492185852863478334475199686, 133392486801388257127953774730008469744261637221272599199572772174870315402893538 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Covering means there are no isolated vertices.
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also covering set-systems with minimum vertex-degree 1.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..12
FORMULA
Inverse binomial transform of A327228.
EXAMPLE
The a(2) = 4 set-systems:
{{1,2}}
{{1},{2}}
{{1},{1,2}}
{{2},{1,2}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]], {n, 0, 3}]
CROSSREFS
The non-covering version is A327228.
The specialization to simple graphs is A327227.
The unlabeled version is A327230.
BII-numbers of these set-systems are A327105.
Cf. A003465, A245797, A327079, A327098, A327103, A327107, A327197.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 01 2019
EXTENSIONS
Terms a(5) and beyond from Andrew Howroyd, Jan 21 2023
STATUS
approved
A327129 Number of connected set-systems covering n vertices with at least one edge whose removal (along with any non-covered vertices) disconnects the set-system (non-spanning edge-connectivity 1). +10
9
0, 1, 2, 35, 2804 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty set-system.
LINKS
Table of n, a(n) for n=0..4.
FORMULA
Inverse binomial transform of A327196.
EXAMPLE
The a(3) = 35 set-systems:
{123} {1}{12}{23} {1}{2}{12}{13} {1}{2}{3}{12}{13}
{1}{13}{23} {1}{2}{12}{23} {1}{2}{3}{12}{23}
{1}{2}{123} {1}{2}{13}{23} {1}{2}{3}{13}{23}
{1}{3}{123} {1}{2}{3}{123} {1}{2}{3}{12}{123}
{2}{12}{13} {1}{3}{12}{13} {1}{2}{3}{13}{123}
{2}{13}{23} {1}{3}{12}{23} {1}{2}{3}{23}{123}
{2}{3}{123} {1}{3}{13}{23}
{3}{12}{13} {2}{3}{12}{13}
{3}{12}{23} {2}{3}{12}{23}
{1}{23}{123} {2}{3}{13}{23}
{2}{13}{123} {1}{2}{13}{123}
{3}{12}{123} {1}{2}{23}{123}
{1}{3}{12}{123}
{1}{3}{23}{123}
{2}{3}{12}{123}
{2}{3}{13}{123}
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1, 0, Length[sys]-Max@@Length/@Select[Union[Subsets[sys]], Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], Union@@#==Range[n]&&eConn[#]==1&]], {n, 0, 3}]
CROSSREFS
The restriction to simple graphs is A327079, with non-covering version A327231.
The version for spanning edge-connectivity is A327145, with BII-numbers A327111.
The BII-numbers of these set-systems are A327099.
The non-covering version is A327196.
Cf. A003465, A006129, A263296, A322395, A323818, A327071, A327149.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Aug 27 2019
STATUS
approved
A327201 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled simple graphs covering n vertices with non-spanning edge-connectivity k. +10
9
1, 0, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 2, 3, 7, 5, 4, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,10
COMMENTS
The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a disconnected or empty graph, ignoring isolated vertices.
LINKS
Table of n, a(n) for n=0..18.
Gus Wiseman, Unlabeled graphs covering 5 vertices, organized by non-spanning edge-connectivity.
EXAMPLE
Triangle begins:
1
{}
0 1
0 0 1 1
1 1 2 2 1
2 3 7 5 4 1 1
CROSSREFS
Row sums are A002494.
Column k = 0 is A327075.
The labeled version is A327149.
Spanning edge-connectivity is A263296.
The non-covering version is A327236 (partial sums).
Cf. A000088, A322338, A322396, A326787, A327076, A327077, A327079, A327126, A327129, A327148, A327235.
KEYWORD
nonn,tabf,more
AUTHOR
Gus Wiseman, Sep 03 2019
STATUS
approved
A327149 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of simple labeled graphs covering n vertices with non-spanning edge-connectivity k. +10
8
1, 0, 1, 0, 0, 3, 1, 3, 12, 15, 10, 1, 40, 180, 297, 180, 60, 10, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,6
COMMENTS
The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty graph.
LINKS
Table of n, a(n) for n=0..18.
FORMULA
A327148(n,k) = Sum_{m = 0..n} binomial(n,m) T(m,k). In words, column k is the inverse binomial transform of column k of A327148.
EXAMPLE
Triangle begins:
1
{}
0 1
0 0 3 1
3 12 15 10 1
40 180 297 180 60 10 1
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1, 0, Length[sys]-Max@@Length/@Select[Union[Subsets[sys]], Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&eConn[#]==k&]], {n, 0, 4}, {k, 0, Binomial[n, 2]}]//.{foe___, 0}:>{foe}
CROSSREFS
Row sums are A006129.
Column k = 0 is A327070.
Column k = 1 is A327079.
The corresponding triangle for vertex-connectivity is A327126.
The corresponding triangle for spanning edge-connectivity is A327069.
The non-covering version is A327148.
The unlabeled version is A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327097, A327099, A327102, A327125, A327129, A327144.
KEYWORD
nonn,tabf,more
AUTHOR
Gus Wiseman, Aug 27 2019
STATUS
approved
page 1 2

Search completed in 0.013 seconds

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 29 11:15 EDT 2024. Contains 375512 sequences. (Running on oeis4.)