Vertex Connectivity

Author

Eric W. Weisstein
August 12, 2023

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

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

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

Table

GraphDataCountTable["VertexConnectivity",Flatten[{
"Andrasfai"->000027,"FibonacciCube"->008620,"HalvedCube"->000217,
(* 0's *) Thread[{"Bishop","Camel","Empty","TriangularHoneycombAcuteKnight","TriangularHoneycombRook","WheelComplement"}->000004],
(* 1's *) Thread[{"Alkane","Barbell","Centipede","DoubleCone","Helm","Pan","Path","Spoke","Star","Sunlet","Web"}->000012],
(* 2's *) Thread[{"Book","Cycle","Gear","Hanoi","HexagonalGrid","MengerSponge","SierpinskiCarpet","SierpinskiGasket","Sun","TriangularGrid"}->007395],
(* 3's *) Thread[{"Apollonian","CrossedPrism","CubeConnectedCycle","Flower","Goldberg","MoebiusLadder","Prism","SierpinskiTetrahedron","StackedPrism","Trapezohedron","Wheel"}->010701],
(* 4's*) Thread[{"Antiprism","TorusGrid"}->010709]
}]]

Parametrized families

<<MathWorld`Graphs`

Alkane

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

FindSequenceFunction[seq,n]

AlternatingGroupGraph

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

Andrasfai

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]//FullSimplify

Antelope n×n

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

Antiprism

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

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

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

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

FindSequenceFunction[seq,n]

BlackBishop n×n

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

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

Bishop n×n

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

Book

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

FindSequenceFunction[seq,n]

Bruhat

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

FindSequenceFunction[seq,n]

Camel n×n

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

Centipede

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

FindSequenceFunction[seq,n]

CocktailParty

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

Complete

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

seq=Table[GraphData[{"Complete",n},"VertexConnectivity"],{n,30}]

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

CompleteBipartite n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

CrossedPrism

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

FindSequenceFunction[seq,n-1]//Factor

Crown

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

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["VertexConnectivity"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"VertexConnectivity"],{n,3,8}]

Cycle

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

seq=Table[GraphData[{"Cycle",n},"VertexConnectivity"],{n,3,30}]

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

CycleComplement

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

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

DiagonalIntersection

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

Dipyramid

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

DoubleCone

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

Empty

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

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

FibonacciCube

A008620

A002264

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

FindSequenceFunction[seq,n]

Table[Ceiling[n/3],{n,15}]

Flower

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

FoldedCube

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

FindSequenceFunction[seq,n]

Gear

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

FindSequenceFunction[seq,n]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"VertexConnectivity"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"VertexConnectivity"],{n,3,20}]

Grid m×n

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

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"VertexConnectivity"],{n,20}]

FindSequenceFunction[seq,n]

Grid k×m×n

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

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"VertexConnectivity"],
(((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}}]["VertexConnectivity"]

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

FindSequenceFunction[seq,n]//FullSimplify

HalvedCube

A000217

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

FindSequenceFunction[seq,n]

Hanoi

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

Helm

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

Hypercube

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

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

FindSequenceFunction[seq,n+1]

Keller

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

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

FindSequenceFunction[seq,n]

King n×n

seq=Table[GraphData[{"King",{n,n}},"VertexConnectivity"],{n,20}]

FindSequenceFunction[seq,n]//Factor

Knight m×n

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

Knight n×n

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

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

Ladder

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

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

FindSequenceFunction[seq,n]//Factor

LadderRung

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

LucasCube

seq=Table[GraphData[{"LucasCube",n},"VertexConnectivity"],{n,15}]

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

Table[Ceiling[n/3],{n,15}]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>4]

A002264

FindSequenceFunction[Drop[seq,4],n-4]//FullSimplify

Table[(1/9) (3+3 n-3 Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((2 n π)/3)]),{n,20}]

FullSimplify[(1/9) (3+3 n-3 Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((2 n π)/3)])/.n->n-2]

Table[(n-Cos[2 (n-2) π/3]+ Sin[2 (n-2) π/3]/Sqrt[3]-1)/3,{n,0,20}]

(1+n-ChebyshevU[n,-(1/2)])/.n->n-2

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

Floor[Range[0,20]/3]

Table[Floor[n/3],{n,0,20}]

FindLinearRecurrence[%]

LinearRecurrence[{1,0,1,-1},{0,0,0,1},20]

FindGeneratingFunction[%,x]

CoefficientList[Series[((x^3)/((((-1+x))^2) (1+x+(x^2)))),{x,0,20}],x]

MengerSponge

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

MoebiusLadder

A010701

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

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

Mycielski

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

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

Odd

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

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

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

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

Pan

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

Path

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

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

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

PathComplement

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

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

Pell

seq=Table[GraphData[{"LucasCube",n},"Pell"],{n,9}]

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

Prism

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

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"VertexConnectivity"],{n,20}]

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

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"VertexConnectivity"],{n,20}]

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

RookComplement n×n

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

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

SierpinskiCarpet

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

FindSequenceFunction[seq,n]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"VertexConnectivity"],{n,5}]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

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

FindSequenceFunction[seq,n]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"VertexConnectivity"],{n,5}]

FindSequenceFunction[seq,n]

StackedBook

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

StackedPrism

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

Star

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

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

FindSequenceFunction[seq,n]//Factor

Sun

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

FindSequenceFunction[seq,n-2]//Factor

Sunlet

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

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

TorusGrid n×n

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

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

Transposition

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

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

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

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["VertexConnectivity"]

seq=Table[GraphData[{"Trapezohedron",n},"VertexConnectivity"],{n,3,20}]

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

Triangular

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

FindSequenceFunction[seq,n-1]

TriangularGrid

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

FindSequenceFunction[seq,n+1]//FullSimplify

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

FindSequenceFunction[seq,n]

TriangularHoneycombRook

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

TriangularSnake

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

Web

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

Wheel

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

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

FindSequenceFunction[seq,n-3]//FullSimplify

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"VertexConnectivity"],{n,4,20}]

FindSequenceFunction[seq,n-3]//FullSimplify

WhiteBishop n×n

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

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

Factor[%]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"VertexConnectivity"],{n,20}]

Checks

l0=Monitor[{g=#,GraphData[#,"VertexConnectivity"],TimeConstrained[System`VertexConnectivity[GraphData[#]],60]}&/@GraphData[All],g];

Cases[l0,{_,_,$Aborted}]

Sort[GraphData[#,{"V","#"}]&/@%[[All,1]]]

GraphData[g={6,57},"LabeledImage"]

GraphData[g,"VertexConnectivity"]

System`VertexConnectivity[GraphData[g]]

Combinatorica`VertexConnectivity[Graph[g]]

VertexDelete[GraphData[g],6]

ConnectedGraphQ[%]

l1=Select[DeleteCases[l0,{_,_,$Aborted}],#[[2]]=!=#[[3]]&]

Select[l1,GraphData[#[[1]],"Disconnected"]&]