Graph Strength

Author

Eric W. Weisstein
September 13, 2022

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

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

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

Definition

Cunningham 1985:

Gusfield 1991:

Algorithm

Figure from Wikipedia:

ee=UndirectedEdge@@@{{3,7},{5,10},{8,11},{9,11}};
g=EdgeAdd[MyGraphUnion[Sequence@@(CompleteGraph/@{5,5,1}),VertexLabels->Automatic],ee]

EncircleGraphVertices[g,{Range[5],Range[6,10],{11}},Method->"BSpline"]

EncircleGraphVertices[g,{Range[5],Range[6,10],{11}}]

RecognizeGraph[g]

TimeConstrained[FindEdgeCuts[g],5]

g=GraphData["ButterflyGraph","Graph","Labeled"]

Strength[g]

Length[#]/(Length[ConnectedComponents[EdgeDelete[g,EdgeList[g][[#]]]]]-1)&/@FindEdgeCuts[g]

Min[%]

cuts=EdgeList[g][[#]]&/@FindEdgeCuts[g];

SortBy[{#,Length[ConnectedComponents[#2]],#/(Length[ConnectedComponents[#2]]-1),#2}&@@@Union[{Length[#],CanonicalGraph[EdgeDelete[g,#]]}&/@cuts],#[[3]]&]

Compare all, minimum, minimal

Strength[GraphData["K4"]]

cuts=FindEdgeCuts[GraphData[{5,31}]]

Strength[GraphData[{5,31}],cuts]

Strength[GraphData[{5,31}]]

GraphData["ButterflyGraph","MinimalEdgeCuts"]/.UndirectedEdge

FindEdgeCuts@GraphData["ButterflyGraph"]

EdgeListToEdgeIndices[g_,cuts_]:=(cuts/.Thread[EdgeList[g]->Range[EdgeCount[g]]])

data=Monitor[
{
gn=#,
g=GraphData[#];
rules=Thread[EdgeList[g]->Range[EdgeCount[g]]];
Strength[g,GraphData[#,"MinimalEdgeCuts"]/.rules],
Strength[g,GraphData[#,"MinimumEdgeCuts"]/.rules],
Strength[g,GraphData[#,"EdgeCuts"]/.rules]
}&/@GraphData["Connected",2;;7],gn];//Timing

Minimum and Minimal give different results:

DeleteCases[data,{_,x_,x_,_}]

Smallest fractions are obtained only when using *all* edge cuts (as opposed to just minimum or minimal cuts):

DeleteCases[data,{_,x_,x_,x_}|{__,_Strength}]

Table

GraphDataCountTable["Strength"]

Parametrized families

Alkane

Inferred for n > 6:

seq=Table[GraphData[{"Alkane",n},"Strength"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Strength"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Strength"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Strength"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Strength"]

Inferred for n > 4:

seq=Table[GraphData[{"Antiprism",n},"Strength"],{n,3,25}]

Table[((4n)/(2n-1)),{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Strength"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

Inferred for n > 2:

seq=Table[GraphData[{"Barbell",n},"Strength"],{n,3,20}]

FindSequenceFunction[seq,n]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Strength"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Strength"],{n,10}]

Book

Inferred for n > 6:

seq=Table[GraphData[{"Book",n},"Strength"],{n,20}]

Table[((3n+1)/(2n+1)),{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Strength"],{n,6}]

FindSequenceFunction[seq,n]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Strength"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Strength"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"Strength"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["Strength"]

Inferred for n > 6:

seq=Table[GraphData[{"Complete",n},"Strength"],{n,20}]

Table[Piecewise[{{Infinity,n==1}},n/2],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Strength"]

DeleteCases[Sort[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Strength"],
((m n)/(m+n-1))
},{n,20},{m,n}],1]],{_,x_,x_}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Strength"]

Inferred for n > 4:

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Strength"],{n,20}]

Table[((n^2)/(2n-1)),{n,20}]

Table[((n^2)/(2n-1)),{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Strength"]

DeleteCases[Sort[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Strength"],
((k m+k n+m n)/(k+m+n-1))
},{n,10},{m,n},{k,m}],2]],{_,x_,x_}]

Inferred for these:

DeleteCases[%,{_,_Missing,_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Strength"]

Inferred for n > 2:

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Strength"],{n,10}]

((k m+k n+m n)/(k+m+n-1))/.{k->n,m->n}

Table[((3(n^2))/(3n-1)),{n,20}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Strength"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

Crown

seq=Table[GraphData[{"Crown",n},"Strength"],{n,20}]

Cycle

Entity["Graph",{"Cycle",n}]["Strength"]

Inferred for n > 19:

seq=Table[GraphData[{"Cycle",n},"Strength"],{n,3,25}]

Table[(n/(n-1)),{n,3,20}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Strength"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Strength"],{n,3,14}]

Dipyramid

Inferred for n > 6:

seq=Table[GraphData[{"Dipyramid",n},"Strength"],{n,3,20}]

Table[((3n)/(n+1)),{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Strength"]

seq=Table[GraphData[{"Empty",n},"Strength"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Strength"],{n,15}]

FindSequenceFunction[seq,n]//Head//Timing

Flower

seq=Table[GraphData[{"Flower",n},"Strength"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"Strength"],{n,2,10}]

FindSequenceFunction[seq,n]

Gear

Inferred for n > 5:

seq=Table[GraphData[{"Gear",n},"Strength"],{n,3,20}]

FindSequenceFunction[seq,n]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Strength"],{n,10}]

Goldberg

seq=Table[GraphData[{"FoldedCube",n},"Strength"],{n,2,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Strength"]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Strength"]

seq=Table[GraphData[{"Grid",{n,n}},"Strength"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Strength"]

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Strength"],
(((k+m+n) (k m n-1))/(3 k m n))
},{n,5},{m,n},{k,m}],2]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Strength"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Strength"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"Strength"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Strength"],{n,5}]

Helm

Inferred for n > 5:

seq=Table[GraphData[{"Helm",n},"Strength"],{n,3,20}]

FindSequenceFunction[seq,n]

Hypercube

Entity["Graph",{"Hypercube",n}]["Strength"]

seq=Table[GraphData[{"Hypercube",n},"Strength"],{n,0,10}]

FindSequenceFunction[seq,n+1]

Keller

Entity["Graph",{"Keller",n}]["Strength"]

seq=Table[GraphData[{"Keller",n},"Strength"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Strength"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Strength"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Strength"]

seq=Table[GraphData[{"Knight",{n,n}},"Strength"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["Strength"]

Inferred for n > 6:

seq=Table[GraphData[{"Ladder",n},"Strength"],{n,20}]

Table[((3n-2)/(2n-1)),{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"Strength"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Strength"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Strength"]

Inferred for n > 5:

seq=Table[GraphData[{"MoebiusLadder",n},"Strength"],{n,3,25}]

Table[((3n)/(2n-1)),{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["Strength"]

seq=Table[GraphData[{"Mycielski",n},"Strength"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["Strength"]

seq=Table[GraphData[{"Odd",n},"Strength"],{n,7}]

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

Pan

Inferred for n > 19:

seq=Table[GraphData[{"Pan",n},"Strength"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["Strength"]

Inferred for n > 18:

seq=Table[GraphData[{"Path",n},"Strength"],{n,20}]

PathComplement

Inferred for n > 7:

seq=Table[GraphData[{"PathComplement",n},"Strength"],{n,20}]

Table[(n/2)-1,{n,20}]

Prism

Entity["Graph",{"Prism",n}]["Strength"]

Inferred for n > 5:

seq=Table[GraphData[{"Prism",n},"Strength"],{n,3,25}]

Table[((3n)/(2n-1)),{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Strength"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Strength"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]//Factor

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Strength"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]//Factor

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"Strength"],{n,4}]

FindSequenceFunction[seq,n]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"Strength"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Strength"],{n,6}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"Strength"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"Strength"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["Strength"]

Inferred for n > 21:

seq=Table[GraphData[{"Star",n},"Strength"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"Strength"],{n,3,20}]

Do[With[{gn={"Sun",n}},Print[{gn,Strength@GraphData[gn]//Timing}]],{n,3,6}]

Sunlet

Inferred for n > 8:

seq=Table[GraphData[{"Sunlet",n},"Strength"],{n,3,20}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"Strength"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Strength"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["Strength"]

seq=Table[GraphData[{"Transposition",n},"Strength"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Strength"],{n,2,10}]

FindSequenceFunction[seq,n-1]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Strength"],{n,0,10}]

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Strength"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Strength"],{n,9}]

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Strength"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Strength"],{n,10}]

FindSequenceFunction[seq,n]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Strength"],{n,10}]

TriangularSnake

Inferred for n > 11:

seq=Table[GraphData[{"TriangularSnake",n},"Strength"],{n,1,20,2}]

Web

Inferred for n > 5:

seq=Table[GraphData[{"Web",n},"Strength"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Strength"]

Inferred for n > 11:

seq=Table[GraphData[{"Wheel",n},"Strength"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Strength"],{n,2,10}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Strength"],{n,10}]

Capobianco and Molluzzo

The strength of a point in a graph is defined as the increase in the number of connected components in the graph upon removal of the point.

$Version

g=With[{s=Sqrt[3]/2},Graph[Range[9],UndirectedEdge@@@{{4,5},{4,6},{5,6},{2,7},{7,8},{8,9},{2,6},{6,7},{3,6}},VertexCoordinates->{{-1,0},{-1/2,s},{1,0},{-1/2,-s},{1/2,-s},{0,0},{1/2,s},{3/2,s},{5/2,s}},VertexLabels->Automatic]]//StyleGraphs

StrengthVector[g_Graph]:=Module[{n=VertexCount[g]},Table[Length[ConnectedComponents[VertexDelete[g,i]]],{i,n}]-Length[ConnectedComponents[g]]]

GraphStrength[g_Graph]:=With[{S=StrengthVector[g]},1/S.S]

StrengthVector[g]

1/S.S

GraphStrength[g]

Table[GraphStrength[PathGraph[Range[n]]],{n,10}]

Table[GraphStrength[StarGraph[n]],{n,10}]