Bridged Graph

Author

Eric W. Weisstein
October 30, 2015

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/BridgedGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/BridgedGraph.html.

©2015 Wolfram Research, Inc. except for portions noted otherwise

Connected Graph Counts

A000088 = simple

A001349 = connected

A263914 = bridgeless

A007146 = bridgeless connected

A000088={1,2,4,11,34,156,1044,12346,274668,12005168,1018997864,165091172592,50502031367952,29054155657235488,31426485969804308768,64001015704527557894928,245935864153532932683719776,1787577725145611700547878190848,24637809253125004524383007491432768};A001349={1,1,2,6,21,112,853,11117,261080,11716571,1006700565,164059830476,50335907869219,29003487462848061,31397381142761241960,63969560113225176176277,245871831682084026519528568,1787331725248899088890200576580,24636021429399867655322650759681644};
A007146={1,0,1,3,11,60,502,7403,197442,9804368,902818087,153721215608,48443044675155,28363687700395422,30996524108446916915,63502033750022111383196,244852545022627009655180986};
A263914={1,1,2,5,16,77,582,8002,205538,10010657};

With[{pair={A001349,A007146}},Subtract@@pair[[All,;;Min[Length/@pair]]]]

Length[%]

A052446

GraphData

Length/@Table[GraphData[{"Bridged","Connected"},n],{n,7}]

Combinatorica

Table[Count[ConnectedGraphs[n,"Format"->"Combinatorica"],_?(Bridges[#]=!={}&)],{n,7}]//Timing

Table[Count[ConnectedGraphs[n,"Format"->"Combinatorica"],_?(Bridges[#]=!={}&)],{n,8}]//Timing

Table[Count[ConnectedGraphs[n],_?(Bridges[#]=!={}&)],{n,8}]//Timing

Table[Count[ConnectedGraphs[n,"Format"->"Combinatorica"],_?(Bridges[#]=!={}&)],{n,9}]//Timing

Graphs.m

$Version

Table[ConnectedGraphs[n],{n,8}];//Timing//AbsoluteTiming

Bridges (Combinatorica)

Context[Bridges]

Table[Count[ConnectedGraphs[n],_?(Bridges[#]=!={}&)],{n,8}]//Timing

Table[Count[ConnectedGraphs[n],_?(Bridges[#]=!={}&)],{n,9}]//Timing

Table[Count[ConnectedGraphs[n],_?(Bridges[#]=!={}&)],{n,10}]//Timing

KEdgeConnectedGraphQ

Table[Count[ConnectedGraphs[n],_?(!KEdgeConnectedGraphQ[#,2]&)],{n,8}]//Timing

Table[Count[ConnectedGraphs[n],_?(!KEdgeConnectedGraphQ[#,2]&)],{n,9}]//Timing

EdgeConnectivity

Table[Count[ConnectedGraphs[n],_?(System`EdgeConnectivity[#]<2&)],{n,8}]//Timing

Table[Count[ConnectedGraphs[n],_?(System`EdgeConnectivity[#]<2&)],{n,9}]//Timing

Simple Graph Counts

With[{pair={A000088,A263914}},Subtract@@pair[[All,;;Min[Length/@pair]]]]

A263915

GraphData

Length/@Table[GraphData["Bridged",n],{n,7}]

Combinatorica

Table[Count[Graphs[n,"Format"->"Combinatorica"],_?(Bridges[#]=!={}&)],{n,7}]//Timing

Table[Count[Graphs[n,"Format"->"Combinatorica"],_?(Bridges[#]=!={}&)],{n,8}]//Timing

Graphs

$Version

Table[Graphs[n],{n,8}];//Timing

Bridges

Context[Bridges]

Table[Count[Graphs[n],_?(Bridges[#]=!={}&)],{n,8}]//Timing

Table[Count[Graphs[n],_?(Bridges[#]=!={}&)],{n,9}]//Timing

Table[Count[Graphs[n],_?(Bridges[#]=!={}&)],{n,10}]//Timing

KEdgeConnectedGraphQ

gs=Select[Graphs[3],(Bridges[#]=!={}&)]

Function[g,KEdgeConnectedGraphQ[#,2]&/@ConnectedGraphComponents[g]]@gs[[1]]

ConnectedGraphComponents[]

Table[Count[Graphs[n],_?(Function[g,Or@@KEdgeConnectedGraphQ[#,2]&/@ConnectedGraphComponents[g]])],{n,8}]//Timing

EdgeConnectivity

Table[Count[ConnectedGraphs[n],_?(System`EdgeConnectivity[#]>1&)],{n,8}]//Timing

Eumeration

v6.1

Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData[],GraphData[#,"Bridged"]&]]//TableForm[#,TableDepth->2]&