Metric Dimension

Author

Eric W. Weisstein
January 21, 2024

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

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

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

Table

GraphDataCountTable["MetricDimension",Join[
{"Barbell"->005843,"CompleteBipartite"->005843,"CompleteTripartite"->008585,"CycleComplement"->057354,"DoubleCone"->090223,"Hypercube"->303735,"Ladder"->040000,"MoebiusLadder"->010702,"Path"->057427,"PathComplement"->057354,"Prism"->176059,"Rook"->004772,"Star"->028310,"Sun"->004523,"TorusGrid"->010702,"Triangular"->004523,"TriangularHoneycombQueen"->004396,"Wheel"->057354},
(* 1,2,... *) Thread[{"Alkane","Andrasfai","CocktailParty","Complete","Crown","TriangularHoneycombBishop"}->000027],
(* 2's *) Thread[{"Cycle",{"Grid",2},"Pan","TriangularSnake","TriangularGrid"}->007395],
(* 3's *) Thread[{"Antiprism",{"Grid",3}}->010701]]]

Definition

Foster-Greenwood and Uhl 2022

Tillquist et al. 2021

Sources

Ali, G.; Laila, R.; and Ali, M.  "Metric Dimension of Some Families of Graph."  {\it Math.\ Sci.\ Lett.} {\bf 5}, 99–102, 2016.  http://www.naturalspublishing.com/files/published/hf8zh948797o57.pdf

Harary, F. and Melter, R.~A. "On the Metric Dimension of a Graph."  {\it Ars Combin.} {\bf 2}, 191–195, 1976.

Slater, P.~J. "Leaves of Trees."  {\it Congr.\ Numer.}, No.~14, 549–559, 1975.

Tillquist, R. C.; Frongillo, R. M.; Lladser, M.E.  "Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications." https://arxiv.org/abs/2104.07201

Foster-Greenwood, B.\ and Uhl, C.  ``Metric Dimension of a Diagonal Family of Generalized Hamming Graphs.''  2 Aug 2022.  https://arxiv.org/abs/2208.01519

Classes

<<MathWorld`Graphs`

Alkane

Inferred for n >= 7:

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

AlternatingGroupGraph

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

Andrasfai

Inferred for n >= 8:

Table[GraphData[{"Andrasfai",n},"MetricDimension"],{n,20}]

Apollonian

Table[GraphData[{"Apollonian",n},"MetricDimension"],{n,6}]

Barbell

Inferred for n >= 11:

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

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

BlackBishop n×n

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

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

Book

Inferred for n > 14:

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

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

Bruhat

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

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

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

CocktailParty

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

Complete

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

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{1,m==n==1}},m+n-2],
GraphData[{"CompleteBipartite",{m,n}},"MetricDimension"]
},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

Inferred for n >= 10:

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
Piecewise[{{2,k==m==n==1},{Max[k,m,n],Max[k,m,n]==k m n}},k+m+n-3],
GraphData[{"CompleteTripartite",{k,m,n}},"MetricDimension"]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

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

Inferred for n >= 7:

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

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

CrossedPrism

Table[GraphData[{"CrossedPrism",n},"MetricDimension"],{n,4,20,2}]

Do[With[{gn={"CrossedPrism",2n}},Print[{gn,MemoryConstrained[MetricDimension[GraphData[gn]],200*^9]//Timing}]],{n,2,10}]

Crown

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

CubeConnectedCycle

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

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

Do[Print[{gn={"CubeConnectedCycle",n},MetricDimension[GraphData[gn]]//Timing}],{n,3,5}]

Cycle

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

Table[GraphData[{"Cycle",n},"MetricDimension"],{n,3,20}]

DiagonalIntersection

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

Do[Print[{gn={"DiagonalIntersection",n},MetricDimension[GraphData[gn]]//Timing}],{n,3,9}]

Dipyramid

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

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

DoubleCone

A090223

Table[GraphData[{"DoubleCone",n},"MetricDimension"],{n,3,20}]

Do[Print[{gn={"DoubleCone",n},MetricDimension[GraphData[gn]]//Timing}],{n,3,20}]

Empty

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

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

FibonacciCube

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

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

Flower

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

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

Gear

https://arxiv.org/pdf/2104.07201.pdf

https://www.ssmr.ro/bulletin/pdf/50-4/artico32mod.pdf

J_2n should be J_2,n ~ Gear

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

Goldberg

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

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

Grid m×n

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

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

Grid n×n

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

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

Grid k×m×n

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

Select[{#,Lookup[GraphData[#,"NotationRules"],"Grid"]}&/@GraphData["Grid"],Length[#[[2]]]==3&]

Grid n×n×n

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

HalvedCube

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

Do[Print[{gn={"HalvedCube",n},MetricDimension[GraphData[gn]]//Timing}],{n,7}]

Hanoi

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

Do[Print[{{"Hanoi",n},MetricDimension[GraphData[{"Hanoi",n}]]//Timing}],{n,5}]

Helm

When dropping first term, matches A350327 and A057364

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

FindSequenceFunction[DeleteMissing@Rest@seq,n-4]

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

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

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

HexagonalGrid n×n×n

Table[GraphData[{"HexagonalGrid",{n,n,n}},"MetricDimension"],{n,5}]

Do[Print[{gn={"HexagonalGrid",{n,n,n}},MetricDimension[GraphData[gn]]//Timing}],{n,5}]

Hypercube

A303735

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

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

p. 12 and the Table 2 on p. 15 and say beta(G_{n_1, ..., n_d}) = d
But Table 1 on p. 14 gives values with beta(Q_k) < k for k >= 5.
Since Q_k ~ G_{2, 2, ...}, are these two statements inconsistent?

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

King m×n

Sort@Flatten[Table[{{m,n},GraphData[{"King",{m,n}},"MetricDimension"]},{n,10},{m,n}],1]

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

King n×n

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

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

Kneser K(n, 2)

Table[GraphData[{"Kneser",{n,2}},"MetricDimension"],{n,3,15}]

Table[Piecewise[{{Missing["NotApplicable"],n==3||n==4},{3,n==5}},Floor[2(n+1)/3]],{n,3,15}]

https://arxiv.org/pdf/1203.2660.pdf

With[{n=#2[[1]],i=Mod[#2[[1]],3]},{
#,
GraphData[#,"MetricDimension"],
2/3(n-i)+i
}]&@@@Cases[{#,GraphData[#,"NotationRules","Kneser"]}&/@GraphData["Kneser"],{_,{_?(GreaterEqualThan[6]),2}}]

(2/3)(n-Mod[n,3])+Mod[n,3]//FullSimplify

Table[(1/3) (2 n+Mod[n,3]),{n,2,50}]

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

%===%%

Knight m×n

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

Entity["Graph",{"Knight",{m,n}}]["Connected"]//InputForm

Sort@DeleteCases[Flatten[Table[{
{m,n},
Piecewise[{{0,m==n==1},{Missing["NotApplicable"],Min[m,n]<3||m==n==3}},X],
GraphData[{"Knight",{m,n}},"MetricDimension"]
},{n,10},{m,n}],1],{_,x_,x_}]

Sort@Flatten[Table[{{m,n},GraphData[{"Knight",{m,n}},"MetricDimension"]},{n,10},{m,n}],1]

Knight n×n

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

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

Do[Print[{gn={"Knight",{n,n}},MetricDimension[GraphData[gn]]//Timing}],{n,6}]

Ladder

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

MoebiusLadder

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

Inferred for n >= 11:

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

Table[(7-(((-1))^n))/2,{n,3,25}]

Table[Piecewise[{{4,Mod[n,2]==1},{3,Mod[n,2]==0}}],{n,3,25}]

Mycielski

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

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

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

Odd

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

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

Do[Print[{gn={"Odd",n},MetricDimension[GraphData[gn]]//Timing}],{n,5}]

Path

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

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

PermutationStar

Table[GraphData[{"PermutationStar",n},"MetricDimension"],{n,6}]

Queen n×n

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

Do[Print[{gn={"Queen",{n,n}},MetricDimension[GraphData[gn]]//Timing}],{n,7}]

Rook m×n

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

rook[m_,n_]:=Piecewise[{{Floor[2/3(n+m-1)],m<=n<=2m-1},{n-1,n>=2m-1}},Missing["NotAvailable"]]

Table[rook[n,n],{n,20}]

Rook n×n

A004772

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

Table[rook[n,n],{n,20}]==seq

SierpinskiCarpet

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

Do[Print[{{"SierpinskiCarpet",n},MetricDimension[GraphData[{"SierpinskiCarpet",n}]]//Timing}],{n,5}]

SierpinskiGasket

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

Do[Print[{{"SierpinskiGasket",n},MetricDimension[GraphData[{"SierpinskiGasket",n}]]//Timing}],{n,5}]

SierpinskiTetrahedron

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

Do[Print[{{"SierpinskiTetrahedron",n},MetricDimension[GraphData[{"SierpinskiTetrahedron",n}]]//Timing}],{n,6}]

StackedBook n×n

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

Do[Print[{gn={"StackedBook",{n,n}},MetricDimension[GraphData[gn]]//Timing}],{n,7}]

Star

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

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

(seq=Table[MetricDimension[StarGraph[n]],{n,15}])//Timing

Table[Piecewise[{{0,n==1},{1,n==2}},n-2],{n,15}]

%==seq

Sun

A004523

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

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

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

Sunlet

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

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

Tetrahedral

Table[GraphData[{"Tetrahedral",n},"MetricDimension"],{n,6,10}]

Do[Print[{gn={"Tetrahedral",n},MetricDimension[GraphData[gn]]//Timing}],{n,6,90}]

TorusGrid m×n

DeleteCases[Sort@Flatten[Table[{
{m,n},
Piecewise[{{4,Mod[m ,2]==0&&Mod[n,2]==0}},3],
GraphData[{"TorusGrid",{m,n}},"MetricDimension"]
},{n,3,10},{m,3,n}],1],{_,x_,x_}|{_,_,_GraphDataX}]//Quiet

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"MetricDimension"],{n,3,20}]

Table[Piecewise[{{3,Mod[n,2]==1},{4,Mod[n,2]==0}}],{n,3,20}]==seq

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

Trapezohedron

Table[GraphData[{"Trapezohedron",n},"MetricDimension"],{n,3,20}]

Do[Print[{gn={"Trapezohedron",n},MetricDimension[GraphData[gn]]//Timing}],{n,3,20}]

Transposition

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

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

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

Triangular

Table[GraphData[{"Triangular",n},"MetricDimension"],{n,2,20}]

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

Do[Print[{gn={"Triangular",n},MetricDimension[GraphData[gn]]//Timing}],{n,2,20}]

https://arxiv.org/pdf/1203.2660.pdf

With[{n=#2[[1]],i=Mod[#2[[1]],3]},{
#,
GraphData[#,"MetricDimension"],
2/3(n-i)+i
}]&@@@Cases[{#,GraphData[#,"NotationRules","Johnson"]}&/@GraphData["Johnson"],{_,{_?(GreaterEqualThan[6]),2}}]

(2/3)(n-Mod[n,3])+Mod[n,3]//FullSimplify

Table[(1/3) (2 n+Mod[n,3]),{n,2,50}]

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

%===%%

TriangularGrid

Inferred for n >=5:

Table[GraphData[{"TriangularGrid",n},"MetricDimension"],{n,10}]

TriangularHoneycombBishop

Inferred for n >= 6:

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

TriangularHoneycombObtuseKnight

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

%/._Missing->"X"

Table[Piecewise[{{0,n==1},{Missing["NotApplicable"];0,1<n<6}},Floor[(n+1)/2]],{n,20}]

Do[Print[{gn={"TriangularHoneycombObtuseKnight",n},MetricDimension[GraphData[gn]]//Timing}],{n,10}]

TriangularHoneycombQueen

A004396

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

Table[Piecewise[{{0,n==1}},Floor[2n/3]]+1,{n,10}]

Do[Print[{gn=GraphData[{"TriangularHoneycombQueen",n},"#"],MetricDimension[GraphData[gn]]//Timing}],{n,10}]

Web

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

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

Wheel

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

A057354

https://arxiv.org/pdf/2104.07201.pdf

Tillquist 2021-04-23: With respect to wheel graphs:
[beta(W_3) = 3; tetrahedral graph]
beta(W_4) = 2
beta(W_5) = 2
beta(W_6) = 3

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

(seq=Table[MetricDimension[WheelGraph[n]],{n,4,19}])//Timing

beta[n_]:=With[{n0=n-1},Piecewise[{
{3,n==4||n==7},
{3+2Floor[(n-7)/5],(Mod[n0,5]==2||Mod[n0,5]==3)},
{4+2Floor[(n-9)/5],(Mod[n0,5]==4||Mod[n0,5]==0||Mod[n0,5]==1)}
}]]

Table[beta[n],{n,4,17}]

%==%252

beta[n_]:=Piecewise[{
{3,n==4||n==7},
{3+2Floor[(n-8)/5],(Mod[n-1,5]==2||Mod[n-1,5]==3)},
{4+2Floor[(n-10)/5],(Mod[n-1,5]==4||Mod[n-1,5]==0||Mod[n-1,5]==1)}
}]

Table[beta[n],{n,4,18}]

%==%252

beta[n_]:=Piecewise[{
{3,n==4||n==7},
{3+2Floor[(n-8)/5],(Mod[n,5]==3||Mod[n,5]==4)},
{4+2Floor[(n-10)/5],(Mod[n,5]==0||Mod[n,5]==1||Mod[n,5]==2)}
}]

Table[beta[n],{n,4,17}]

%==%252

beta[n_]:=Piecewise[{
{3,n==4||n==7},
{4+2Floor[(n-10)/5],Mod[n,5]<3},
{3+2Floor[(n-8)/5],Mod[n,5]>=3}
}]

Table[beta[n],{n,4,19}]

%==seq

beta[n_]:=Piecewise[{{3,n==4||n==7}},Floor[2n/5]]

Table[beta[n],{n,4,19}]

Table[Piecewise[{{3,n==4||n==7}},Floor[2n/5]],{n,4,19}]

Table[MetricDimension[WheelGraph[n]],{n,4,19}]

%=={3,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7}

WhiteBishop n×n

Inferred for n >= 7:

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

Zebra n×n

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

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

Tests

test=Sort[GraphData[#,{"MetricDimension","V","#"}]&/@GraphData["MetricDimension","Defined"]];

(bad=DeleteCases[Monitor[{g=#,GraphData[#,"MetricDimension"],TimeConstrained[MetricDimension[GraphData[#]],1]}&/@Take[test[[All,-1]],All],g],{_,x_,x_}])//Timing

Cases[bad,{g_,_,$Aborted}:>g]

DeleteCases[bad,{_,_,$Aborted}]

Table[MetricDimension[AntiprismGraph[n]],{n,3,10}]

Table[MetricDimension[CompleteGraph[n]],{n,10}]

Table[MetricDimension[CycleGraph[n]],{n,3,10}]

Table[MetricDimension[PrismGraph[n]],{n,3,7}]

Table[MetricDimension[PathGraph[Range[n]]],{n,7}]