Biconnected Graph

Author

Eric W. Weisstein
December 7, 2021

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

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

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

Counts

Cf. A002218

GraphData

Table[Length[GraphData["Biconnected",n]],{n,7}]

Combinatorica

Table[ConnectedGraphs[i,"Format"->"Combinatorica"],{i,9}];

Table[Count[ConnectedGraphs[i,"Format"->"Combinatorica"],_?BiconnectedQ],{i,8}]//Timing

Table[Count[ConnectedGraphs[i],_?BiconnectedQ],{i,9}]//Timing

Graphs.m

Load:

Table[ConnectedGraphs[i],{i,10}];//AbsoluteTiming

ArticulationVertices (Combinatorica)

Context[ArticulationVertices]

Table[Count[ConnectedGraphs[i],_?(ArticulationVertices[#]==={}&)],{i,8}]//Timing

Table[Count[ConnectedGraphs[i],_?(ArticulationVertices[#]==={}&)],{i,9}]//Timing

Table[Count[ConnectedGraphs[i],_?(ArticulationVertices[#]==={}&)],{i,10}]//Timing

VertexConnectivity

Table[Count[ConnectedGraphs[i],_?(VertexConnectivity[#]>1&)],{i,8}]//Timing

Table[Count[ConnectedGraphs[i],_?(VertexConnectivity[#]>1&)],{i,9}]//Timing

Table[Count[ConnectedGraphs[i],_?(VertexConnectivity[#]>1&)],{i,10}]//Timing

KVertexConnectedGraphQ

Table[Count[ConnectedGraphs[i],_?(KVertexConnectedGraphQ[#,2]&)],{i,8}]//Timing

Table[Count[ConnectedGraphs[i],_?(KVertexConnectedGraphQ[#,2]&)],{i,9}]//Timing

Table[Count[ConnectedGraphs[i],_?(KVertexConnectedGraphQ[#,2]&)],{i,10}]//Timing

FindVertexCut

Table[Count[ConnectedGraphs[i],_?(Length[FindVertexCut[#]]>1&)],{i,7}]//Timing

Graphic

TextGrid[b={#[[1,1]],Length[#],#[[All,2]]}&/@SplitBy[Sort[GraphData[#,{"V","#"}]&/@GraphData["Biconnected",3;;5]],First],Dividers->All]

GraphicsGrid[Map[Show[GraphData[#]//StyleGraphs[#,VertexSize->{"Scaled",.08}]&,PlotLabel->TextCell[GraphData[#,"Name"],TextAlignment->Center,PageWidth->75],
LabelStyle->Directive[Black,Italic,FontFamily->"Times"]]&,Flatten[Partition[#,UpTo[5]]&/@b[[All,-1]],1],{2}],ImageSize->400,Dividers->All]

Connected but Not Biconnected

TextGrid[cnotb={#[[1,1]],Length[#],#[[All,2]]}&/@SplitBy[Sort[GraphData[#,{"V","#"}]&/@Select[GraphData["Connected",;;5],!GraphData[#,"Biconnected"]&]],First],Dividers->All]

GraphicsGrid[Map[Show[StyleGraphs[GraphData[#],VertexSize->If[#==="SingletonGraph",.03,{"Scaled",.08}]],PlotLabel->TextCell[GraphData[#,"Name"],TextAlignment->Center,PageWidth->75],
LabelStyle->Directive[Black,Italic,FontFamily->"Times"]]&,Flatten[Partition[#,UpTo[5]]&/@cnotb[[All,-1]],1],{2}],ImageSize->400,Dividers->All]