Fixing Number

Author

Eric W. Weisstein
January 30, 2024

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

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

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

Definition

https://arxiv.org/pdf/1807.04372.pdf

Fixing Numbers of Graphs and Groups
Courtney R. Gibbons, Joshua D. Laison
2018

Debra Boutin. Identifying graph automorphisms using determining sets. Electron. J. Combin., 13(1):Research Paper 78, approx. 14 pp. (electronic), 2006.

David Erwin and Frank Harary. Destroying automorphisms by fixing nodes. Discrete Math., 306(24):3244–3252, 2006.

Karen Collins and Joshua D. Laison. Fixing numbers of Kneser graphs. preprint, 2008.

Graphs for which the greedy algorithm returns nonoptimal value

Figure

greedyexceptions={"GreenfieldGraph","FolkmanGraph",{"Cubic",{16,20}},{"RegularNonplanarDiameter",{3,3,16,3}}};

(greedyvalues=Sort[{
GraphData[#,"VertexCount"],
FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"],
FixingNumber[GraphData[#],Method->"Greedy"],
#
}&/@greedyexceptions])//Timing

TextGrid[greedyvalues,Dividers->All]

GraphicsRow[Show[StyleGraphs@GraphData[#4],PlotLabel->Column[{GraphData[#4,"Name"],Row[{"fix: ",#2}],Row[{Subscript["fix","greedy"],": ",#3}]},Alignment->Center],LabelStyle->Directive[Black,Italic,FontFamily->"Times New Roman"]]&@@@greedyvalues,ImageSize->1000,Spacings->-20]

Computation for GraphData graphs

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Select[
Complement[GraphData[;;20],GraphData["CompleteKPartite",;;20]],
GraphData[#,"FixingNumber"]<6&
],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Select[
Complement[GraphData[;;20],GraphData["CompleteKPartite",;;20]],
GraphData[#,"FixingNumber"]<8&],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

{"BananaTree", {7, 4}} needs 35+ GB

GraphData[{"BananaTree",{7,4}},"FixingNumber"]

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Select[
Complement[GraphData[21;;30],GraphData["CompleteKPartite",21;;30]],
GraphData[#,"FixingNumber"]<7&],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Computation for n-node graphs

Do[
Print[{
n,
DeleteCases[
{
#,
FixingNumber[#],
FixingNumber[#,Method->"IncrementalSymmetricallyDistinctVertices"]
}&/@ConnectedGraphs[n],
{_,x_,x_}]//Timing
}],
{n,10}]

Polyhedral graphs with fix # == 3

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

https://arxiv.org/pdf/1708.07354.pdf

FixingNumber[GraphData[#]]&/@{"K4","TriakisTetrahedralGraph","CubicalGraph","TetrakisHexahedralGraph","RhombicDodecahedralGraph","IcosahedralGraph","OctahedralGraph","SmallTriakisOctahedralGraph"}

DeleteCases[SortBy[Select[GraphData["Polyhedral"],GraphData[#,"FixingNumber"]==3&],GraphData[#,"V"]&],{"Dipyramid",_Integer?(GreaterThan[3])}]

GraphData/@%//StyleGraphs

GraphDataCountTable

<<MathWorld`Graphs`

GraphDataCountTable["FixingNumber"]

Parametrized families

Alkane

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

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

AlternatingGroupGraph

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

Do[Print[{gn=GraphData[{"AlternatingGroupGraph",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,2,6}]

Andrasfai

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

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

Antelope n×n

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

Do[Print[{gn=GraphData[{"Antelope",{n,n}},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,15}]

Do[Print[{{"Antelope",{n,n}},FixingNumber[AntelopeGraph[n,n]]//Timing}],{n,16,20}]

Antiprism

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

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

Do[Print[{gn=GraphData[{"Antiprism",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,3,25}]

Apollonian

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

Do[Print[{gn=GraphData[{"Apollonian",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,5}]

Barbell

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

Do[Print[{gn=GraphData[{"Barbell",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,3,20}]

BlackBishop n×n

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

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

Bishop n×n

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

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

Book

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

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

Bruhat

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

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

Camel n×n

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

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

Centipede

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

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

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

FindSequenceFunction[seq,n]//FullSimplify

CompleteTripartite k×m×n

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

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

CompleteTripartite n×n×n

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

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

CrossedPrism

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

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

Crown

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

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

CubeConnectedCycle

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

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

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

Cycle

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

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

Table[FixingNumber[CycleGraph[n]],{n,3,20}]

CycleComplement

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

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

DiagonalIntersection

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

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,4,14}]

Dipyramid

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

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

DoubleCone

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

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

Empty

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

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

FibonacciCube

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

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

Flower

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

FoldedCube

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

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,3,10}]

Gear

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

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

Giraffe n×n

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

Goldberg

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

Grid m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"FixingNumber"],
Piecewise[{{0,m==n==1},{2,m==n==2||m==n==3}},1]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

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

Grid k×m×n

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"FixingNumber"],
Piecewise[{{1,Mod[k m n,2]==0},{2,Min[k,m,n]==2||Mod[k m n,2]==1}}]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

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

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

Do[Print[{{"Grid",{n,n,n}},FixingNumber[GridGraph[{n,n,n}]]//Timing}],{n,20}]

HalvedCube

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

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

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],FixingNumber[GraphData[gn],Method->"IncrementalSymmetricallyDistinctVertices"]//Timing}],{n,10}]

Hanoi

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

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

Helm

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

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

Hypercube

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

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

Do[Print[{gn=GraphData[{"Hypercube",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,0,9}]

Keller

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

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

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

Do[Print[{gn=GraphData[{"Keller",n},"#"],FixingNumber[GraphData[gn],Method->"IncrementalSymmetricallyDistinctVertices"]//Timing}],{n,{2}}]

King n×n

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

Do[Print[{gn=GraphData[{"King",{n,n}},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,20}]

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"FixingNumber"],
Piecewise[{
{0,m==n==0},
{Max[m,n]-1,Min[m,n]==1},{2,m==n==3||(Min[m,n]==3&&Max[m,n]==5)||(Min[m,n]==3&&Max[m,n]==7)},{3,m==n==2||(Min[m,n]==2&&Max[m,n]==3)||(Min[m,n]==3&&Max[m,n]==6)},
{4,m==n==4||Min[m,n]==2}},1]
},{n,10},{m,n}],1],{_,x_,x_}]

Table[FixingNumber[KnightGraph[2,n]],{n,20}]

Table[FixingNumber[KnightGraph[3,n]],{n,20}]

Table[FixingNumber[KnightGraph[4,n]],{n,20}]

Table[FixingNumber[KnightGraph[5,n]],{n,20}]

Table[FixingNumber[KnightGraph[6,n]],{n,20}]

Print[{gn=GraphData[{"Knight",#},"#"],FixingNumber[GraphData[gn]]//Timing}]&/@Sort[GraphData[#,"NotationRules","Knight"]&/@GraphData[{"Nonempty","Knight"}]]

Knight n×n

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

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

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

Ladder

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

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

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

LadderRung

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

MengerSponge

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

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

MoebiusLadder

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

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

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

Mycielski

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

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

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

Odd

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

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

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

Pan

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

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

Path

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

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

Table[FixingNumber[PathGraph[Range[n]]],{n,20}]

PathComplement

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

Prism

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

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Do[Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],FixingNumber[GraphData[gn]]//Timing}],{n,6}]

Spoke n×n

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

StackedBook

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

StackedPrism

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

Star

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

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

Table[FixingNumber[StarGraph[n]],{n,20}]

Sun

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

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

Sunlet

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

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

TorusGrid n×n

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

Transposition

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

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

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

Trapezohedron

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

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

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

Triangular

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

TriangularGrid

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

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

FindSequenceFunction[seq,n]

TriangularSnake

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

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

Web

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

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

Wheel

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

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

WheelComplement

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

FindSequenceFunction[seq,n-3]//FullSimplify

WhiteBishop n×n

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

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

Zebra n×n

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

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

Algorithm

https://arxiv.org/pdf/1807.04372.pdf

Greedy

Answer to question #1: no; Greenfield provided a graph on 12 nodes for which the algorithm can produce 3 or 4

FranklinGraph [12 nodes] (Greenfield says 2 but it's 3)

GraphData["FranklinGraph","V"]

GraphData["FranklinGraph","Graph",7]

DegenerateGraphEmbeddingTypes[]

FixingNumber[GraphData["FranklinGraph"],Method->"Greedy",Debug->True]

FixingNumber[GraphData["FranklinGraph"],Method->"IncrementalSubsets",Debug->True]

FixingNumber[GraphData["FranklinGraph"],Method->"IncrementalSymmetricallyDistinctVertices"]

GoldnerHararyGraph [11 nodes] (Greenfield's graph is missing 4 vertices)

GraphData["GoldnerHararyGraph","V"]

GraphData["GoldnerHararyGraph","Graph","All"]

GraphData["GoldnerHararyGraph","FixingNumber"]

RecognizeGraph[]

VertexCount[]

FixingNumber[GraphData[{"NonhamiltonianPolyhedral",{11,49}}],Method->"Greedy",Debug->True]

GreenfieldGraph [12 nodes] (greedy gives 3 or 4; correct is 3)

Consequently, the algorithm is clearly guaranteed to construct a minimal fixing set, but as we will see below it is not necessarily minimum.

GraphData["GreenfieldGraph"]

FixingNumber[GraphData["GreenfieldGraph"],Method->"GreedyIncremental"]

Wrong!

FixingNumber[GraphData["GreenfieldGraph"],Method->"IncrementalSubsets"]

Algorithm comparisons

GreedyIncremental

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"GreedyIncremental"]}&/@GraphData[;;15],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Greedy

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"Greedy"]}&/@GraphData[;;15],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

IncrementalSymmetricallyDistinctVertices

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Complement[GraphData[;;12],GraphData["CompleteKPartite",;;12]],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Complement[GraphData[13],GraphData["CompleteKPartite",13]],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSymmetricallyDistinctVertices"]}&/@Complement[GraphData[14],GraphData["CompleteKPartite",14]],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

IncrementalSubsets

Monitor[data={gn=#,GraphData[#,"FixingNumber"],FixingNumber[GraphData[#],Method->"IncrementalSubsets"]}&/@Complement[GraphData[;;12],GraphData["CompleteKPartite",;;12]],gn];//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Compute

SortBy[Select[GraphData[All],MissingQ[GraphData[#,"FixingNumber"]]&],GraphData[#,"V"]&]

Monitor[
data={
gn=#,
GraphData[#,"FixingNumber"],
FixingNumber[GraphData[#]]
}&/@Select[todo,MissingQ@GraphData[#,"FixingNumber"]&],
gn]//Timing

DeleteCases[data,{_,x_,x_}|{_,_Missing,_}]

Cases[data,{__,_?FailureQ}]

l={#,{0,#3}}&@@@DeleteCases[
data,
{_,x_,x_}|{"GreenfieldGraph",__}|{__,_?FailureQ}
]