Block

Author

Eric W. Weisstein
December 8, 2023

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

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

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

Examples

bug(406189): KVertexConnectedComponents[..., 2] treats isolated dipoles and singletons inconsistently

Harary, p. 26

s=Sqrt[3]/2;
v1={{0,0},{s,0},{s,1/2},{s,-1/2},{2s,0},{2s+1,0},{3s+1,-1/2},{3s+1,1/2},{2s+1-1/4,s/2},{2s+1+1/4,s/2}};
g1=Graph[Range[Length[v1]],UndirectedEdge@@@{{1,3},{1,4},{2,3},{2,4},{3,5},{4,5},{5,6},{6,7},{6,8},{6,9},{6,10},{7,8},{9,10}},VertexCoordinates->v1]

blocks1=Blocks[g1]

indices1=VertexList/@blocks1

CommunityGraphPlot[g1,indices1,Method->None]

GraphicsRow[EncircleGraphVertices[g1,indices1,Method->#]&/@{"RegionDilation","BSpline"},Spacings->-50]

West, p. 155

s=Sqrt[3]/2;
v2={{0,-1/2},{0,1/2},{s,0},{s+1,0},{2s+1,1/2},{2s+1,-1/2},{3s+1,0},{s,1},{s+1,1},{s,-1},{s+1,-1}};
g2=Graph[Range[Length[v2]],UndirectedEdge@@@{{1,2},{1,3},{2,3},{3,4},{4,5},{4,6},{5,6},{5,7},{6,7},{8,9},{10,11}},VertexCoordinates->v2]

blocks2=Blocks[g2]

indices2=VertexList/@blocks2

GraphicsRow[EncircleGraphVertices[g2,indices2,Method->#]&/@{"RegionDilation","BSpline"},Spacings->-50]

Together

GraphicsRow[{graphic1,graphic2},Spacings->-60]

GraphicsRow[{gg1,gg2},Spacings->-100,ImageSize->700]

MathWorld

(g=Graph[Range[7],UndirectedEdge@@@{{1,7},{2,5},{2,6},{3,4},{3,6},{3,7},{4,6},{4,7},{5,6}},VertexLabels->Automatic])//StyleGraphs

r=RecognizeGraph[g]

TwoConnectedComponentNames[g_Graph]:=RecognizeGraph[Subgraph[g,#],"Cache"->"InternalOnly"]&/@KVertexConnectedComponents[g,2]

TwoConnectedComponentNames[GraphData[{7,396}]]

Sort[Sort/@KVertexConnectedComponents[g,2]]

Misc

g=MyGraphUnion[GraphData["2P2+K1"],GraphData[{"Barbell",3}],GraphData["BowtieGraph"],VertexLabels->Automatic]

BlockIndices[g]

Sort[Sort/@KVertexConnectedComponents[g,2]]

but K1 and P2 components are not 2-connected

"2P2+K1

g=GraphData["2P2+K1"]

EdgeList[g]

g=Graph[Range[5],UndirectedEdge@@@{{1,4},{2,5}}]

BlockIndices[g]

Sort[Sort/@KVertexConnectedComponents[g,2]]

"P2+K1

g=GraphData["P2+K1"]

g=Graph[Range[3],UndirectedEdge@@@{{1,2}}]

BlockIndices[g]

Sort[Sort/@KVertexConnectedComponents[g,2]]

"K1"

g=Graph[{1},{},ImageSize->Tiny]

BlockIndices[g]

KVertexConnectedComponents[g,2]

"P2"

g=PathGraph[{1,2}]

BlockIndices[g]

Sort[Sort/@KVertexConnectedComponents[g,2]]

Combinatorica

g=Graphs[7][[427]];
v=Vertices[g];
Print[BiconnectedComponents[g]];
Show[Graphics[{
Table[Text[ToString[i],v[[i]]+{.1,.1}],{i,Length[v]}],
PointSize[.05],
graphic[g]},
AspectRatio->Automatic],PlotRange->All];

Counts

A002218

Table[Length[Select[GraphData["Connected",n],GraphData[#,"BlockCount"]===1&]],{n,7}]

Cf.

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

Parametrized families

GraphDataCountTable["BlockCount"]

Andrasfai

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

Antelope m×n

DeleteCases[Sort[Flatten[Table[{{m,n},XXX,GraphData[{"Antelope",{m,n}},"BlockCount"]},{n,2,10},{m,2,n}],1]],{_,x_,x_}]

Antelope n×n

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

Antiprism

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

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

Apollonian

seq=Table[GraphData[{"Apollonian",n},"BlockCount"],{n,6}]

Barbell

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

Bishop m×n

DeleteCases[Sort[Flatten[Table[{{m,n},Piecewise[{{0,Min[m,n]==1},{2(n-1),Min[m,n]==2},{3,m==n==3}},2],GraphData[{"Bishop",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Bishop n×n

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

BlackBishop m×n

DeleteCases[Sort[Flatten[Table[{{m,n},Piecewise[{
{0,Min[m,n]==1||m==n==2},
{1,m==n==3},
{4,Min[m,n]==3&&Max[m,n]==4},
{Mod[m,2]+1,m==n},
{Max[m,n]-2,Min[m,n]==2},
{n+1,n==m+1},
{Min[m,n],Mod[Min[m,n],2]==0}
},XXX],GraphData[{"BlackBishop",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

BlackBishop n×n

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

Table[Piecewise[{{0,n==1||n==2},{1,n==3}},1+Mod[n,2]],{n,10}]

Table[Binomial[n^2,GraphData[{"BlackBishop",{n,n}},"VertexConnectivity"]],{n,10}]

Book

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

Bruhat

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

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

Sort@DeleteCases[Flatten[Table[{{m,n},Piecewise[{{Max[m,n],Min[m,n]==1}},1],GraphData[{"CompleteBipartite",{m,n}},"BlockCount"]},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[
{{k,m,n},
1,
GraphData[{"CompleteTripartite",{k,m,n}},"BlockCount"]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

Inferred for (some of) these:

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

Inferred for n==7

Table[GraphData[{"DorogovtsevGoltsevMendes",n},"Block"],{n,7}]

Empty

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

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

FibonacciCube

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

Fiveleaper m×n

DeleteCases[Sort[Flatten[Table[{{m,n},0,GraphData[{"Fiveleaper",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"BlockCount"],{n,10}]

FoldedCube

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

Gear

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

Grid m×n

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

DeleteCases[Flatten[Table[{{m,n},Piecewise[{{1,m n<=2},{Max[m,n]-1,Min[m,n]==1}},1],GraphData[{"Grid",{m,n}},"BlockCount"]},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

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

Grid k×m×n

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

DeleteCases[Flatten[Table[{{k,m,n},
Piecewise[{{1,k m n<=2},{Max[k,m,n]-1,k m n/Max[k,m,n]==1}},1],
GraphData[{"Grid",{k,m,n}},"BlockCount"]},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

Helm

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

HexagonalGrid n×n×n

seq=Table[GraphData[{"HexagonalGrid",{n,n,n}},"BlockCount"],{n,5}]

Hypercube

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

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

Keller

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

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

King m×n

DeleteCases[Sort[Flatten[Table[{{m,n},
Piecewise[{{0,m n==2},{Max[m,n]-1,Min[m,n]==1}},1],
GraphData[{"King",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

King n×n

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

Knight m×n

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

DeleteCases[Sort[Flatten[Table[{{m,n},
Piecewise[{{Max[m,n],Min[m,n]==1},{2,m==n==3},{4,Min[m,n]==2&&Max[m,n]<=3},{2(Max[m,n]-2),Min[m,n]==2}},1],
GraphData[{"Knight",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

PathComplement

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

Prism

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

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

Rook m×n

DeleteCases[Sort[Flatten[Table[{{m,n},
Piecewise[{{0,m n<3}},1],
GraphData[{"Rook",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Rook n×n

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

RookComplement m×n

DeleteCases[Sort[Flatten[Table[{
{m,n},
Piecewise[{{0,Min[m,n]==1},{2,m==n==2}},1],
GraphData[{"RookComplement",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Inferred for these:

RookComplement n×n

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

Queen m×n

DeleteCases[Sort[Flatten[Table[{
{m,n},
Piecewise[{{0,m n<3}},1],
GraphData[{"Queen",{m,n}},"BlockCount"]},{n,10},{m,n}],1]],{_,x_,x_}]

Queen n×n

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

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"BlockCount"],{n,4}]

StackedBook n×n

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

StackedPrism n×n

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

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

TorusGrid m×n

DeleteCases[Sort[Flatten[Table[{{m,n},1,GraphData[{"TorusGrid",{m,n}},"BlockCount"]},{n,3,10},{m,3,n}],1]],{_,x_,x_}]

TorusGrid n×n

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

Transposition

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

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

Triangular

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombKing

seq=Table[GraphData[{"TriangularHoneycombKing",n},"BlockCount"],{n,11}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

TriangularSnake

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

Web

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

Wheel

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

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

WhiteBishop m×n

DeleteCases[Sort[Flatten[Table[{
{m,n},
Piecewise[{{0,m==n==2},{Max[m,n]-1,Min[m,n]==2}},1],
GraphData[{"WhiteBishop",{m,n}},"BlockCount"]},{n,2,10},{m,2,n}],1]],{_,x_,x_}]

WhiteBishop n×n

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