Block Graph

Author

Eric W. Weisstein
November 8, 2022

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

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

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

Source

https://en.wikipedia.org/wiki/Block_graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

Block graphs are exactly the graphs for which, for every four vertices u, v, x, and y, the largest two of the three distances d(u,v) + d(x,y), d(u,x) + d(v,y), and d(u,y) + d(v,x) are always equal.

Figure

GraphicsGrid[Flatten[Partition[#,UpTo[5]]&/@Map[Show[GraphData[#]//StyleGraphs,PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Opacity[1],Black,Italic,14,FontFamily->"Times"]],PageWidth->500/5,TextAlignment->Center]]&,
Table[GraphData[{"Connected","Block"},n],{n,5}],{2}],1],ImageSize->700,Dividers->{{Thick,{True},Thick},{Thick,Thick,Thick,Thick,Thick,True,Thick}}]

Classes

GraphClassesThatAreClass["Block"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Block"])

Counts

Connected

A035053

Table[Count[ConnectedGraphs[n],_?BlockGraphQ],{n,9}]//Timing

Length/@Table[GraphData[{"Connected","Block"},n],{n,9}]//Timing

Not-necessarily Connected

Table[Count[Graphs[n],_?BlockGraphQ],{n,9}]//Timing

Length/@Table[GraphData["Block",n],{n,9}]//Timing

Parametrized families

<<MathWorld`Graphs`

Alkane

Table[GraphData[{"Alkane",n},"Block"],{n,10}]

AlternatingGroupGraph

Table[GraphData[{"AlternatingGroupGraph",n},"Block"],{n,2,6}]

Do[Print[{GraphData[{"AlternatingGroupGraph",n},"#"],BlockGraphQ@GraphData[{"AlternatingGroupGraph",n}]//Timing}],{n,2,6}]

Andrasfai

Table[GraphData[{"Andrasfai",n},"Block"],{n,10}]

Do[Print[{GraphData[{"Andrasfai",n},"#"],BlockGraphQ@GraphData[{"Andrasfai",n}]//Timing}],{n,10}]

Antelope n×n

Table[GraphData[{"Antelope",{n,n}},"Block"],{n,15}]

Antiprism

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

Table[GraphData[{"Antiprism",n},"Block"],{n,3,25}]

Do[Print[{GraphData[{"Antiprism",n},"#"],BlockGraphQ@GraphData[{"Antiprism",n}]//Timing}],{n,3,25}]

Apollonian

Table[GraphData[{"Apollonian",n},"Block"],{n,5}]

Do[Print[{GraphData[{"Apollonian",n},"#"],BlockGraphQ@GraphData[{"Apollonian",n}]//Timing}],{n,5}]

Barbell

Table[GraphData[{"Barbell",n},"Block"],{n,3,20}]

Do[Print[{GraphData[{"Barbell",n},"#"],BlockGraphQ@GraphData[{"Barbell",n}]//Timing}],{n,3,20}]

BlackBishop n×n

Table[GraphData[{"BlackBishop",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Bishop",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Book

Table[GraphData[{"Book",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Book",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

Bruhat

Table[GraphData[{"Bruhat",n},"Block"],{n,6}]

Do[Print[{gn=GraphData[{"Bruhat",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,6}]

Camel n×n

Table[GraphData[{"Camel",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Camel",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Centipede

Table[GraphData[{"Centipede",n},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Centipede",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

CocktailParty

Table[GraphData[{"CocktailParty",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"CocktailParty",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Complete

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

Table[GraphData[{"Complete",n},"Block"],{n,30}]

Do[Print[{gn=GraphData[{"Complete",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

Table[GraphData[{"CompleteBipartite",{n,n}},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"CompleteBipartite",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

CompleteTripartite k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
Piecewise[{{True,k m n==Max[k,m,n]}},False],
GraphData[{"CompleteBipartite",{m,n}},"Block"]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

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

Table[GraphData[{"CompleteTripartite",{n,n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"CompleteTripartite",{n,n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

CrossedPrism

Table[GraphData[{"CrossedPrism",2n},"Block"],{n,2,10}]

Do[Print[{gn=GraphData[{"CrossedPrism",2n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Crown

Table[GraphData[{"Crown",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Crown",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

CubeConnectedCycle

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

Table[GraphData[{"CubeConnectedCycle",n},"Block"],{n,3,8}]

Do[Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,8}]

Cycle

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

Table[GraphData[{"Cycle",n},"Block"],{n,3,30}]

Do[Print[{gn=GraphData[{"Cycle",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,30}]

CycleComplement

Table[GraphData[{"CycleComplement",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"CycleComplement",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

DiagonalIntersection

Table[GraphData[{"DiagonalIntersection",n},"Block"],{n,3,14}]

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,14}]

Dipyramid

Table[GraphData[{"Dipyramid",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Dipyramid",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Empty

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

Table[GraphData[{"Empty",n},"Block"],{n,30}]

Do[Print[{gn=GraphData[{"Empty",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"Block"],{n,15}]

Do[Print[{gn=GraphData[{"FibonacciCube",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,15}]

Flower

Table[GraphData[{"Flower",n},"Block"],{n,5,20}]

Do[Print[{gn=GraphData[{"Flower",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,5,20}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"Block"],{n,2,10}]

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Gear

Table[GraphData[{"Gear",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Gear",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Giraffe m×n

GraphData[#,"Block"]&/@GraphData["Giraffe"]

Giraffe n×n

Table[GraphData[{"Giraffe",{n,n}},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Giraffe",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

Goldberg

Table[GraphData[{"Goldberg",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Goldberg",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Grid m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
Piecewise[{{True,Min[m,n]==1}},False],
GraphData[{"Grid",{m,n}},"Block"]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

Table[GraphData[{"Grid",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Grid k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
Piecewise[{{True,Max[k,m,n]==k m n}},False],
GraphData[{"Grid",{k,m,n}},"Block"]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

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

Table[GraphData[{"Grid",{n,n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

HalvedCube

Table[GraphData[{"HalvedCube",n},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Hanoi

Table[GraphData[{"Hanoi",n},"Block"],{n,5}]

Do[Print[{gn=GraphData[{"Hanoi",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,5}]

Helm

Table[GraphData[{"Helm",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Helm",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Hypercube

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

Table[GraphData[{"Hypercube",n},"Block"],{n,0,10}]

Do[Print[{gn=GraphData[{"Hypercube",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,0,10}]

Keller

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

Table[GraphData[{"Keller",n},"Block"],{n,5}]

Do[Print[{gn=GraphData[{"Keller",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,5}]

King m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
Piecewise[{{True,Min[m,n]==1||m==n==2}},False],
GraphData[{"King",{m,n}},"Block"]
},{n,10},{m,n}],1],{_,x_,x_}]

King n×n

Table[GraphData[{"King",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"King",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Knight m×n

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

DeleteCases[Sort@Flatten[Table[{
{m,n},
Piecewise[{{True,Min[m,n]<3}},False],
GraphData[{"Knight",{m,n}},"Block"]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

Table[GraphData[{"Knight",{n,n}},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Knight",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

Ladder

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

Table[GraphData[{"Ladder",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Ladder",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"Block"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"Block"],{n,3}]

Do[Print[{gn=GraphData[{"MengerSponge",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3}]

MoebiusLadder

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

Table[GraphData[{"MoebiusLadder",n},"Block"],{n,3,25}]

Do[Print[{gn=GraphData[{"MoebiusLadder",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Mycielski

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

Table[GraphData[{"Mycielski",n},"Block"],{n,11}]

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,11}]

Odd

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

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

Do[Print[{gn=GraphData[{"Odd",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,7}]

Pan

Table[GraphData[{"Pan",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Pan",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Path

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

Table[GraphData[{"Path",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Path",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

PathComplement

Table[GraphData[{"PathComplement",n},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"PathComplement",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]

Prism

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

Table[GraphData[{"Prism",n},"Block"],{n,3,25}]

Do[Print[{gn=GraphData[{"Prism",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Queen m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Queen"],
Piecewise[{{True,Min[m,n]==1}},False],
GraphData[#,"Block"]}&/@GraphData["Queen"],{_,x_,x_}]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

Rook m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Rook"],
Piecewise[{{True,Min[m,n]==1}},False],
GraphData[#,"Block"]}&/@GraphData["Rook"],{_,x_,x_}]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"Rook",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

RookComplement m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","RookComplement"],
Piecewise[{{True,Min[m,n]<2||m==n==2}},False],
GraphData[#,"Block"]}&/@GraphData["RookComplement"],{_,x_,x_}]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"RookComplement",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"Block"],{n,4}]

Do[Print[{gn=GraphData[{"SierpinskiCarpet",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,4}]

SierpinskiGasket

Table[GraphData[{"SierpinskiGasket",n},"Block"],{n,5}]

Do[Print[{gn=GraphData[{"SierpinskiGasket",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"Block"],{n,6}]

Do[Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,4}]

StackedBook m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","StackedBook"],
XXX,
GraphData[#,"Block"]}&/@GraphData["StackedBook"],{_,x_,x_}]

StackedBook n×n

Table[GraphData[{"StackedBook",{n,n}},"Block"],{n,10}]

Do[Print[{gn=GraphData[{"StackedBook",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,10}]

StackedPrism m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","StackedPrism"],
XXX,
GraphData[#,"Block"]}&/@GraphData["StackedPrism"],{_,x_,x_}]

StackedPrism n×n

Table[GraphData[{"StackedPrism",{n,n}},"Block"],{n,3,5}]

Do[Print[{gn=GraphData[{"StackedPrism",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,5}]

Star

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

Table[GraphData[{"Star",n},"Block"],{n,25}]

Do[Print[{gn=GraphData[{"Star",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,25}]

Sun

Table[GraphData[{"Sun",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sun",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sunlet",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

TorusGrid m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","TorusGrid"],
False,
GraphData[#,"Block"]}&/@GraphData["TorusGrid"],{_,x_,x_}]

TorusGrid n×n

Table[GraphData[{"TorusGrid",{n,n}},"Block"],{n,3,10}]

Do[Print[{gn=GraphData[{"TorusGrid",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,10}]

Transposition

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

Table[GraphData[{"Transposition",n},"Block"],{n,6}]

Do[Print[{gn=GraphData[{"Transposition",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,6}]

Triangular

Table[GraphData[{"Triangular",n},"Block"],{n,2,10}]

Do[Print[{gn=GraphData[{"Triangular",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,2,10}]

TriangularGrid

Table[GraphData[{"TriangularGrid",n},"Block"],{n,0,10}]

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,0,10}]

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Block"],{n,20}]

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"Block"],{n,9}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Block"],{n,20}]

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"Block"],{n,10}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"Block"],{n,10}]

TriangularSnake

Table[GraphData[{"TriangularSnake",n},"Block"],{n,1,20,2}]

Do[Print[{gn=GraphData[{"TriangularSnake",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,1,20,2}]

Web

Table[GraphData[{"Web",n},"Block"],{n,3,20}]

Do[Print[{gn=GraphData[{"Web",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Wheel

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

Table[GraphData[{"Wheel",n},"Block"],{n,4,20}]

Do[Print[{gn=GraphData[{"Wheel",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WheelComplement

Table[GraphData[{"WheelComplement",n},"Block"],{n,4,20}]

Do[Print[{gn=GraphData[{"WheelComplement",n},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"Block"],{n,2,10}]

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Zebra m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Zebra"],
XXX,
GraphData[#,"Block"]}&/@GraphData["Zebra"],{_,x_,x_}]

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"Block"],{n,20}]

Do[Print[{gn=GraphData[{"Zebra",{n,n}},"#"],BlockGraphQ@GraphData[gn]//Timing}],{n,20}]