

A327072


Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.


7



1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,9


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 (2edgeconnected graphs).
Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.


LINKS

Table of n, a(n) for n=0..20.
Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.


EXAMPLE

Triangle begins:
1
1 0
0 1 0
1 0 3 0
10 12 0 16 0
253 200 150 0 125 0


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]]]]]]]]];
Table[If[n<=1&&k==0, 1, Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#, i]]<nLength[csm[Delete[#, i]]]>1, {i, Length[#]}], True]==k&]]], {n, 0, 4}, {k, 0, n}]


CROSSREFS

Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.
Column k = 1 is A327073.
Column k = n  1 is A000272.
Row sums are A001187.
The unlabeled version is A327077.
Row sums without the first column are A327071.
Cf. A001349, A007146, A052446, A054592, A059166, A322395, A327069, A327148.
Sequence in context: A119957 A028852 A319202 * A327377 A095200 A090460
Adjacent sequences: A327069 A327070 A327071 * A327073 A327074 A327075


KEYWORD

nonn,more,tabl


AUTHOR

Gus Wiseman, Aug 24 2019


STATUS

approved



