Graph Toughness

Author

Eric W. Weisstein
February 26, 2023

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

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

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

Table

GraphDataCountTable["Toughness",Join[
(* 0 *) Thread[{"Bishop","Camel","Empty","LadderRung","TriangularHoneycombAcuteKnight","TriangularHoneycombRook","WheelComplement"}->000004],
(* 1, 2, 3, *) Thread[{"CocktailParty","Rook","RookComplement"}->000027],
(* 1 *) Thread[{"CompleteBipartite","Crown","Cycle","Ladder","Trapezohedron"}->000012],
(* 2 *) Thread[{"Antiprism","CompleteTripartite"}->007395],
{"WhiteBishop"->004526}]]

Parametrized families

Alkane

Inferred for n>5

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

Do[Print[{n,Toughness@GraphData[{"Alkane",n}]//Timing}],{n,5}]

FindSequenceFunction[seq,n]

AlternatingGroupGraph

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

Andrasfai

Inferred for n > 7:

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

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]//FullSimplify

Antelope n×n

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

Antiprism

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

Inferred for n > 7

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

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

Inferred for n > 9

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

FindSequenceFunction[seq,n]

BlackBishop n×n

Inferred for n > 6:

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

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

Bishop n×n

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

Book

Inferred for n > 8

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

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

Bruhat

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

FindSequenceFunction[seq,n]

Camel n×n

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

Centipede

Inferred for n>9

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

FindSequenceFunction[seq,n]

CocktailParty

Inferred for n > 10:

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

Table[n-1,{n,20}]

Complete

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

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

CompleteBipartite m×n

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

Chvátal 1973:

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Toughness"],
Piecewise[{{Infinity,m==n==1}},m/n]
},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

Min[k,m,n]+(k+m+n-Min[k,m,n]-Max[k,m,n])

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Toughness"],
Piecewise[{{Infinity,k==m==n==1}},((k+m+n)/(Max[k,m,n]))-1]
},
{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

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

Inferred for n > 4

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

CrossedPrism

Inferred for n > 6:

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

Crown

Inferred from n > 7

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

Cycle

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

Inferred for n > 13

seq=Table[GraphData[{"Cycle",n},"Toughness"],{n,3,20}]

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

CycleComplement

Inferred for n > 14

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

Table[Piecewise[{{0,n==4}},((n-3)/2)],{n,3,20}]

DiagonalIntersection

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

Dipyramid

Inferred for n > 11:

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

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

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Toughness"],{n,3,20}]

Empty

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

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

FibonacciCube

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

Flower

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

FoldedCube

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

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],Toughness[GraphData[gn]]//Timing}],{n,2,6}];

Gear

Inferred for n > 8

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

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

Giraffe n×n

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

Goldberg

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

Grid m×n

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

Grid n×n

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

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

FindSequenceFunction[seq,n]

Grid k×m×n

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

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Toughness"],
XXX
},{n,5},{m,n},{k,m}],2]

Grid n×n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

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

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]

Hanoi

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

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

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

Helm

Inferred for n > 8

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

FindSequenceFunction[seq,n]

Hypercube

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

Inferred for n > 4:

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

Keller

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

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

FindSequenceFunction[seq,n]

King n×n

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

FindSequenceFunction[seq,n]//Factor

Knight m×n

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

Knight n×n

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

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

Ladder

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

Inferred for n > 1

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

FindSequenceFunction[seq,n]//Factor

LadderRung

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

MengerSponge

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

MoebiusLadder

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

Inferred for n > 10

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

Do[Print[{gn={"MoebiusLadder",n},Toughness[GraphData[gn]]//Timing}],{n,3,8}];

Table[Piecewise[{{(n/(n-1)),Mod[n,2]==0},{1,Mod[n,2]==1}}],{n,3,25}]

Mycielski

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

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

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

Odd

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

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

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

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

Pan

Inferred for n > 18

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

Path

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

Inferred for n > 18

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

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

PathComplement

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

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

Prism

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

Inferred for n > 10:

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

Do[Print[{gn={"Prism",n},Toughness[GraphData[gn]]//Timing}],{n,3,8}];

Table[Piecewise[{{1,Mod[n,2]==0},{(n/(n-1)),Mod[n,2]==1}}],{n,3,25}]

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

Queen n×n

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

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],Toughness[GraphData[gn]]//Timing}],{n,5}];

Rook m×n

Chvátal 1973:

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Rook",{m,n}},"Toughness"],
Piecewise[{{Infinity,Min[m,n]==1}},(m+n)/2-1]
},{n,10},{m,n}],1],{_,x_,x_}]

Rook n×n

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

RookComplement m×n

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"RookComplement",{m,n}},"Toughness"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

RookComplement n×n

Inferred for n > 5:

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

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

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiSieve

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

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]

(seq=Table[Toughness[SierpinskiTetrahedronGraph[n]],{n,7}])//Timing

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

StackedBook

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

StackedPrism

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

Star

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

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

Table[Piecewise[{{Infinity,n==1||n==2}},(1/(n-1))],{n,25}]

Sun

Inferred for n > 10

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

Do[Print[{gn={"Sun",n},Toughness[GraphData[gn]]//Timing}],{n,3,8}];

Sunlet

Inferred for n > 7

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

Tetrahedral

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

TorusGrid n×n

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

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

Transposition

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

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

(seq=Table[Toughness[TranspositionGraph[n]],{n,7}])//Timing

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Triangular

Inferred for n > 7:

seq=Table[GraphData[{"Triangular",n},"Toughness"],{n,2,20}]

Do[Print[{gn=GraphData[{"Triangular",n},"#"],Toughness[GraphData[gn]]//Timing}],{n,2,7}];

TriangularGrid

Inferred for n > 5:

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

Do[Print[{gn={"TriangularGrid",n},Toughness[GraphData[gn]]//Timing}],{n,6}];

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

Inferred for n > 6:

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

Do[Print[{gn=GraphData[{"TriangularHoneycombBishop",n},"#"],Toughness[GraphData[gn]]//Timing}],{n,9}];

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

FindSequenceFunction[seq,n]

TriangularHoneycombRook

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

TriangularSnake

Inferred for n == 19

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

Web

Inferred for n > 6

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

Wheel

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

Inferred for n >11

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

Toughness@GraphData[{"Wheel",4}]

Table[Piecewise[{{∞,n==4}},((Ceiling[n/2])/(Ceiling[n/2]-1))],{n,4,20}]

WhiteBishop n×n

Inferred for n > 7:

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

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],Toughness[GraphData[gn]]//Timing}],{n,2,6}];

Table[Ceiling[n/2]-1,{n,2,10}]

Zebra n×n

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

Algorithm

data=Monitor[{
gn=#,
Toughness[GraphData[#],GraphData[#,"MinimalVertexCuts"]],
Toughness[GraphData[#],GraphData[#,"MinimumVertexCuts"]],
Toughness[GraphData[#],GraphData[#,"VertexCuts"]]
}&/@GraphData["Connected",;;7],gn];//Timing

Minimum and Minimal give different results:

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

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

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

Cases[data,{{"Gear",3},__}]

g=GraphData[{"Gear",3},"Graph","Labeled"]//StyleGraphs

cuts=FindVertexCuts[g=GraphData[{"Gear",3}]]

Length[#]/Length[ConnectedComponents[VertexDelete[g,#]]]&/@cuts

Position[%136,3/4]

Length[#]/Length[ConnectedComponents[VertexDelete[g,#]]]&/@Select[cuts,Length[#]==2&]

cuts[[13]]

GraphicsGrid[{
{g,Style[Overscript["⟶",{2,3}],18],VertexDelete[g,{2,3}]},
{g,Style[Overscript["⟶",{2,3,4}],18],VertexDelete[g,{2,3,4}]}
},ImageSize->500,Spacings->{-100,Automatic},Dividers->{None,All}]

Complete

Toughness[CompleteGraph[4]]

CompleteBipartite

Toughness1[CompleteGraph[{4,5}]]

Toughness2[CompleteGraph[{4,5}]]

Rook

Toughness[RookGraph[2,5]]

(1/2)(2+5)-1

Hamiltonian graphs with Toughness < 1

Cases[{#,GraphData[#,"Toughness"]}&/@GraphData["Hamiltonian"],{_,_?(LessThan[1])}]

Nonhamiltonian graphs with Toughness ≥ (Subscript[t, 0])

τ ≥ 1

TextGrid[{#[[All,1]],#[[1,2]]}&/@SplitBy[SortBy[DeleteCases[Cases[{#,GraphData[#,"Toughness"]}&/@GraphData["Nonhamiltonian"],{_,_?(GreaterEqualThan[1])}],{_,∞}],N[Last[#]]&],Last],Dividers->All]

{7, 631}

Chvatal's counterexample:

e[l__Integer]:=Sequence@@Partition[{l},2,1]

s=Sqrt[3]/2;
v=Join[{{0,0}},CirclePoints[3],CirclePoints[{1/2,Pi/2-Pi/10},3]];
g=Graph[Range[7],UndirectedEdge@@@{e[4,2,3,4,1,3,5,1,2,7,1,6,4]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

GraphData[%,"Graph","All"]

τ ≥ 2

Bauer, D.; Broersma, H. J.; and Veldman, H. J.  "Not Every 2-Tough Graph Is Hamiltonian."  Disc. Appl. Math. 99, 317–321, 2000.  https://doi-org.proxy2.library.illinois.edu/10.1016/S0166-218X(99)00141-9