Weisfeiler-Leman Dimension

Author

Eric W. Weisstein
June 8, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Weisfeiler-LemanDimension.nb.

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

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

Special cases

Disconnected

https://www.iti.zcu.cz/wl2018/pdf/wl2018_schweitzer.pdf

DistanceHereditary ≤ 2

https://arxiv.org/abs/2005.11766

the Weisfeiler-Leman dimension of the class of finite distance-hereditary graphs is equal to 2 (i.e., a distance-hereditary graph has WL dimension ≤ 2)

Forest == 1

Planar ≤ 3

https://arxiv.org/pdf/2305.17302v1.pdf

paper [12], which is directly related to what follows. It is proved there that the WL-dimension of every planar graph is at most 3.

Polyhedral ≤ 2 (under certain conditions)

https://arxiv.org/abs/2305.17302v1

Regular == 1 with exceptions

https://www.iti.zcu.cz/wl2018/pdf/wl2018_schweitzer.pdf

https://arxiv.org/pdf/2005.11766.pdf

GraphData[{"Cycle",5},"ComplementGraph","Name"]

Only regular graphs with (Subscript[dim, WL])==1 are complete, empty, cocktail party, ladder rung, 5-cycle,

The proofs can be found in [1, Lemma 3.1(a)] and [9, Theorem 2.1], respectively.

[1] V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky, Graph Isomorphism, Color Refinement, and Compactness, Computational Complexity, 26, no. 3, 627–685 (2017).

[9] F. Fuhlbrück, J Köbler, and O. Verbitsky, Identiability of graphs with small color classes by the Weisfeiler-Leman algorithm, in: Proc. 37th International Symposium on Theoretical Aspects of Computer Science, Dagstühl Publishing, Germany (2020), pp. 43:1-43:18.

Bounds

Cases[GraphData[#,{"#","V","WeisfeilerLemanDimension"}]&/@GraphData[All],{_,x_,x_}]

Keifer 2020

Li et. al.

https://arxiv.org/pdf/2305.17302v1.pdf

Characterization

1

https://arxiv.org/pdf/2305.17302v1.pdf

The graphs of WL-dimension 1 have completely been characterized in [1] and independently in [13]

2

https://arxiv.org/pdf/2305.17302v1.pdf

A complete description of the graphs of WL-dimension 2 seems to be hopeless (it would imply a description of all strongly regular graphs identified by the parameters up to isomorphism);

Embeddings

<<MathWorld`Graphs`

Import["https://arxiv.org/pdf/2305.17302v1.pdf",{"PageGraphics",19}]

Column[Row/@Map[Show[GraphData["LiPonomarenkoZemanGraph"<>#],PlotLabel->#]&,{{"X10","X18","X20","X32"},{"Y42","X48","Y50"},{"X42","X50"}},{2}],Alignment->Center]

GraphData["LiPonomarenkoZemanGraph"<>#,"#"]&/@Flatten[{{"X10","X18","X20","X32"},{"Y42","X48","Y50"},{"X42","X50"}}]

GraphDataCountTable

<<MathWorld`Graphs`

GraphDataCountTable["WeisfeilerLemanDimension"]

Parametrized families

Alkane

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

AlternatingGroupGraph

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

Andrasfai

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

Antelope n×n

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

Antiprism

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

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

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

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

FindSequenceFunction[seq,n]

BlackBishop n×n

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

Bishop n×n

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

Book

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

FindSequenceFunction[seq,n]

Bruhat

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

Camel n×n

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

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

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

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

DoubleCone

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

Empty

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

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

FibonacciCube

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

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

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

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

Goldberg

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

Grid m×n

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

Grid n×n

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

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

Grid k×m×n

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

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

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

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

Keller

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

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

King n×n

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

Knight m×n

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

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

PathComplement

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

Prism

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook

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

StackedPrism

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

Star

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

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

Sun

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

Sunlet

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

TorusGrid n×n

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

Transposition

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

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

Trapezohedron

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

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

Triangular

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

TriangularSnake

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

Web

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

Wheel

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

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

FindSequenceFunction[seq,n-3]//FullSimplify

WheelComplement

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

WhiteBishop n×n

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

Zebra n×n

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

GraphDataString

file=OpenWrite["~/weisfeiler.m"]

With[{X="Y",n=VertexCount[g]},
WriteString[file,GraphDataString[
g,
"StandardName"->"LiPonomarenkoZemanGraph"<>X<>ToString[n],
"Name"->"Li\[Hyphen]Ponomarenko\[Hyphen]Zeman graph "<>X<>ToString[n],
"Notation"->Subscript[X,n],
"Skip"->{"Arboricity","Bandwidth","ConstructionNumber","GracefulLabeling","GracefulLabelings","MaximumIndependentEdgeSetCount","MaximumIndependentEdgeSets","MinimumCyclicEdgeCutCount","MinimumCyclicEdgeCuts","Minors","TotalDominationPolynomial","TuttePolynomial"}
]]]

Close[file]