k-Connected Graph

Author

Eric W. Weisstein
July 21, 2020

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/k-ConnectedGraph.nb.

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

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

1-Connected

(HyperlinkTemplate[A001349, https://oeis.org/A001349None, https://oeis.org/A001349, HyperlinkActionRecycled, HyperlinkActive, , ])

Length/@Table[Select[Graphs[n],ConnectedGraphQ],{n,8}]//Timing

Length/@Table[Select[Graphs[n],ConnectedGraphQ],{n,8}]//RepeatedTiming

Length/@Table[Select[Graphs[n],KVertexConnectedGraphQ[#,1]&],{n,8}]//Timing

Length/@Table[Select[Graphs[n],KVertexConnectedGraphQ[#,1]&],{n,8}]//RepeatedTiming

First[%/%%]

bug((HyperlinkTemplate[395887, https://bugs.wolfram.com/show?number=395887None, https://bugs.wolfram.com/show?number=395887, HyperlinkActionRecycled, HyperlinkActive, , ])): KVertexConnectedGraphQ[g, 1] is 1500x slower than ConnectedGraphQ[g]

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

2-Connected

(HyperlinkTemplate[A002218, https://oeis.org/A002218None, https://oeis.org/A002218, HyperlinkActionRecycled, HyperlinkActive, , ])

But differs in a(1) == 1

bug((HyperlinkTemplate[395814, https://bugs.wolfram.com/show?number=395814None, https://bugs.wolfram.com/show?number=395814, HyperlinkActionRecycled, HyperlinkActive, , ])): Address inconsistency between documentation and implementation of KVertexConnectedComponents [for P_2]

Length/@Table[Select[Graphs[n],KVertexConnectedGraphQ[#,2]&],{n,8}]//Timing

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

Table

connectivity = k

cnx=Table[VertexConnectivity/@Graphs[n],{n,8}];//Timing

With[{nmax=Length[cnx]},TextGrid[Table[Count[cnx[[n]],k],{k,0,nmax},{n,nmax}],Dividers->All,Alignment->Decimal]]

TextGrid[counts={{1,1,2,5,13,44,191,1229,13588},{0,1,1,3,11,56,385,3994,67014},{0,0,1,2,7,39,332,4735,113176},{0,0,0,1,2,13,111,2004,66410},{0,0,0,0,1,3,21,345,13429},{0,0,0,0,0,1,3,34,992},{0,0,0,0,0,0,1,4,54},{0,0,0,0,0,0,0,1,4},{0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0}},Dividers->All,Alignment->Decimal]

k-connected

(Subscript[K, 1]) is 1-connected but has vertex connectivity 0
(Subscript[P, 2]) is 2-connected but has vertex connectivity 1

TextGrid[With[{nmax=Length[cnx]},Table[Boole[n==k&&n≤2]+Count[cnx[[n]],_?(#>=k&)],{k,nmax},{n,nmax}]],Dividers->All,Alignment->Decimal]

Compute from counts (Euler transform?) but need to handle (Subscript[K, 1]) and (Subscript[P, 2]) specially

kconnected=Transpose[Reverse/@(Accumulate/@Reverse/@Transpose[Rest[counts]])]

TextGrid[kconnected,Dividers->All,Alignment->Decimal]