|
|
A327231
|
|
Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).
|
|
8
|
|
|
0, 0, 1, 3, 18, 250, 5475, 191541, 11065572, 1104254964, 201167132805, 69828691941415, 47150542741904118, 62354150876493659118, 161919876753750972738791, 827272271567137357352991705, 8331016130913639432634637862600, 165634930763383717802534343776893928
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A bridge is an edge whose removal disconnected the graph, while an endpoint is a vertex belonging to only one edge. The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a graph whose edge-set is disconnected or empty.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(2) = 1 through a(4) = 18 edge-sets:
{12} {12} {12}
{13} {13}
{23} {14}
{23}
{24}
{34}
{12,13,24}
{12,13,34}
{12,14,23}
{12,14,34}
{12,23,34}
{12,24,34}
{13,14,23}
{13,14,24}
{13,23,24}
{13,24,34}
{14,23,24}
{14,23,34}
|
|
MATHEMATICA
|
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]]]]]]]]];
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[#]==1&]], {n, 0, 4}]
|
|
CROSSREFS
|
Connected bridged graphs (spanning edge-connectivity 1) are A327071.
BII-numbers of set-systems with non-spanning edge-connectivity 1 are A327099.
Covering set-systems with non-spanning edge-connectivity 1 are A327129.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|