Domination Number

Author

Eric W. Weisstein
January 30, 2024

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[DominationNumber/@Graphs[n],{n,7}])//Column

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/DominationNumber"];

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames["*.m"]))//Column

A263284

Flatten[tallies]

A000088

Total/@tallies

Interesting:

tallies[[All,1]]

Length/@tallies

Not in OEIS:

Total/@values

By γ

γ==1

Select[GraphData["Connected"],GraphData[#,"DominationNumber"]==1&]

Select[GraphData[{"Bipartite","Connected"}],GraphData[#,"DominationNumber"]==1&]

Intersection@@(GraphData[#,"Classes"]&/@Select[GraphData["Connected"],GraphData[#,"DominationNumber"]==1&])

γ==2

Intersection@@(GraphData[#,"Classes"]&/@Select[GraphData["Connected"],GraphData[#,"DominationNumber"]==2&])

γ==3

Intersection@@(GraphData[#,"Classes"]&/@Select[GraphData["Connected"],GraphData[#,"DominationNumber"]==3&])

γ<3

Intersection@@(GraphData[#,"Classes"]&/@Select[GraphData["Connected"],GraphData[#,"DominationNumber"]<3&])

Theorems

Planar with diam==2, then γ≤3

Henning and Yeo 2013, Theorem 6.1, p. 55

Select[Intersection[GraphData["Planar"],GraphData["DominationNumber","Defined"]],GraphData[#,"Diameter"]==2&&GraphData[#,"DominationNumber"]>3&]

Planar with diam==2, then γ≤2 except for (Subscript[G, 9])

Select[Intersection[GraphData["Planar"],GraphData["DominationNumber","Defined"]],GraphData[#,"Diameter"]==2&&GraphData[#,"DominationNumber"]>2&]

Henning and Yeo 2013, Theorem 6.1, p. 55-56

G9 is the  unique planar graph of diameter two with domination number 3

Goddard, W., Henning, M.A.: Domination in planar graphs with small diameter. J. GraphTheory 40, 1–25 (2002)

Henning and Yeo 2013, p.

g=System`Graph[Range[9],UndirectedEdge@@@Sort[Sort/@Join[
Partition[{1,2,3,4},2,1,1],
Partition[{7,3,6,2,5,1,8,4},2,1,1],
{{7,9},{9,5},{6,9},{9,8}}
]],VertexCoordinates->Join[CirclePoints[4],CirclePoints[{.35,0},4],{{0,0}}]]

RecognizeGraph[g]

FindDominatingSet[g]

SetProperty[g,VertexLabels->"Name"]

EdgeList[g]

Length[%]

g2=System`Graph[EdgeList[g],VertexLabels->"Name"]

Round[20ToCommonEdges[g2,g]/1.634536145576477`]/10

GraphData

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

WriteString[file,GraphDataString[g,
"StandardName"->"GoddardHenningGraph",
"Name"->"Goddard\[Hyphen]Henning graph",
Debug->True
]]

Close[file]

Table

GraphDataCountTable["DominationNumber",{"Alkane"->000027,"AlternatingGroupGraph","Andrasfai"->158799,"Antelope"->369129,"Antiprism"->057354,"Apollonian"->291773,"Barbell"->007395,"Bishop"->000027,"BlackBishop"->004525,"Book"->007395,"Bruhat","Centipede"->000027,"CocktailParty"->007395,"Complete"->000012,"CompleteBipartite"->040000,{"CompleteTripartite",3}->040000,"CrossedPrism"->052928,"Crown"->007395,"CubeConnectedCycle"->296855,"Cycle"->052928,"DiagonalIntersection"->301338,"Dipyramid"->040000,"DorogovtsevGoltsevMendes"->115098,"Empty"->000027,"FibonacciCube"->291295,"Fiveleaper"->369130,"FoldedCube"->271520,"Gear"->052928,"Giraffe"->369133,{"Grid",2}->104519,{"Grid",3}->269706,"HalvedCube"->029866,"Hanoi"->122983,"Helm"->000027,"Hypercube"->000983,"Keller"->010709,"King"->075561,"Knight"->006075,"Ladder"->004526,"LadderRung"->000027,"LucasCube"->364653,"MengerSponge"->306244,"MoebiusLadder"->004525,"Mycielski"->028310,"Odd"->296852,"Pan"->004526,"Path"->004526,"PathComplement"->040000,"PermutationStar"->000142,"Prism"->004524,"Queen"->075458,"Rook"->000027,"RookComplement","SierpinskiCarpet"->291775,"SierpinskiSieve"->000244,"SierpinskiTetrahedron"->002023,{"StackedBook",2}->000027,"Star"->000012,"Sun"->004526,"Sunlet"->000027,"Tetrahedral"->347782,"TorusGrid"->094087,"Transposition"->347790,"Trapezohedron"->007395,"Triangular"->004526,"TriangularGrid"->251419,"TriangularHoneycombAcuteKnight"->289903,"TriangularHoneycombBishop"->110654,"TriangularHoneycombObtuseKnight"->251534,"TriangularHoneycombQueen"->229803,"TriangularHoneycombRook"->000027,"TriangularSnake"->004526,"Web"->000027,"Wheel"->000012,"WhiteBishop"->004524,"Zebra"->369131}]

Parametrized families

<<MathWorld`Graphs`

Andrasfai

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

Table[DominationNumber[AndrasfaiGraph[n]],{n,40}]//Timing

Table

Antelope

A369129

seq=Table[GraphData[{"Antelope",{n,n}},"DominationNumber"],{n,20}]

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

Do[Print[{gn={"Antelope",n},Flatten[{set=Flatten@FindDominatingSet[AntelopeGraph[n,n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,30}]

Antiprism

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

A057354

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

Table[DominationNumber[AntiprismGraph[n]],{n,3,40}]//Timing

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

seq=Table[GraphData[{"Antiprism",n},"DominationNumber"],{n,3,20}]

Table[Exponent[GraphData[{"Antiprism",n},"DominationPolynomial"][x],x,Min],{n,3,20}]

Apollonian

=== ConnectedDominationNumber

A291773

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

seq=Table[If[n<3,1,(3^(n-3)+5)/2],{n,20}]

FindSequenceFunction[Drop[seq,2],n-2]

FullSimplify[%]

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

Join[{1,1},Table[(3^n+135)/54,{n,3,20}]]

Join[{1,1},(3^Range[3,20]+135)/54]

FindLinearRecurrence[Drop[seq,2]]

Join[{1,1},LinearRecurrence[{4,-3},{3,4},20]]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((1-3 x+2 (x^2)-5 (x^3))/(1-4 x+3 (x^2))),{x,0,20}],x]

Barbell

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

BipariteKneser

bk=Sort[{"BipartiteKneser"/.GraphData[#,"NotationRules"],GraphData[#,"DominationNumber"]}&/@GraphData["BipartiteKneser"]]

Cases[bk,{{_,1},d_}:>d]

Cases[bk,{{_,2},d_}:>d]

Cases[bk,{{n_,3},d_}:>{n,d}]

Cases[bk,{{n_,4},d_}:>{n,d}]

Bishop n×n

Table[Floor[n/4]+Ceiling[n/4]+Floor[(n+1)/4]+Floor[(n+2)/4],{n,100}]==Range[100]

FullSimplify[Floor[n/4]+Ceiling[n/4]+Floor[(n+1)/4]+Floor[(n+2)/4]-n,n∈Integers]

PiecewiseExpand[Floor[n/4]+Ceiling[n/4]+Floor[(n+1)/4]+Floor[(n+2)/4]]

BlackBishop n×n

A004525

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

Table[Floor[n/4]+Ceiling[n/4],{n,10}]

Do[Print[{{"BlackBishop",{n,n}},{Length[set=FindDominatingSet[BlackBishopGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,50}]

Book

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

Bruhat

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

Camel

seq=Table[GraphData[{"Camel",{n,n}},"DominationNumber"],{n,20}]

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

Do[Print[{gn={"Camel",{n,n}},Flatten[{set=Flatten@FindDominatingSet[CamelGraph[n,n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,30}]

Centipede

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

CocktailParty

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

Complete

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

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

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

CompleteBipartite n×n

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

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

seq={"CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"DominationNumber"]}&/@GraphData["CompleteBipartite"]//Column

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"DominationNumber"],{n,6}]

DeleteCases[Block[{k,m,n},{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],If[Min[k,m,n]==1,1,2],GraphData[#,"DominationNumber"]}&/@GraphData["CompleteTripartite"]],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",n},"DominationNumber"],{n,4,20,2}]

Table[2Floor[(n+2)/4],{n,4,20,2}]

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

Crown

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

CubeConnectedCycle

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

A296855

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

FindSequenceFunction[seq,n-2]

Cycle

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

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

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

DorogovtsevGoltsevMendes

A115098

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"DominationNumber"],{n,0,7}]

Table[Piecewise[{{1,n==0||n==1}},((3^(n-2))+3)/2],{n,0,15}]

Table[(3^n+3)/2,{n,0,20}]

(3^Range[0,20]+3)/2

FindLinearRecurrence[%]

LinearRecurrence[{4,-3},{2,3},20]

Do[Print[{{"DorogovtsevGoltsevMendes",n},{0,Length@Flatten@FindDominatingSet@DorogovtsevGoltsevMendesGraph[n]//Timing}}],{n,0,15}]

Empty

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

seq=Table[GraphData[{"Empty",n},"DominationNumber"],{n,20}]

FindSequenceFunction[seq,n]

FibonacciCube

A291295

Ilic, A. and Milosevic, M.  "The Parameters of Fibonacci and Lucas Cubes."  Ars Math. Contemp. 12, 25–29, 2017.

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

Do[Print[{gn={"FibonacciCube",n},Flatten[{set=Flatten@FindDominatingSet[FibonacciCubeGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,10}]

Running on byblis65 2022-01-10:

{"Fibonacci", 12}

 143520624 111802701   57.85368   73  210   60.00000   54.60225  9.00%  93.4 59825s

Cutting planes:
  Gomory: 6
  Zero half: 31

Explored 143525477 nodes (13410879790 simplex iterations) in 60042.95 seconds
Thread count was 16 (of 32 available processors)

Solution count 10: 60

Solve interrupted (error code 10001)
Best objective 6.000000000000e+01, best bound 5.500000000000e+01, gap 8.3333%

NArgMin::ntcnvx: The optimization was not solved by convex methods.
"time: 952093."
"set: $Failed"

https://www.solver.com/help/analytic-solver/Out-of-memory

This message can sometimes appear for very large, difficult LP/MIP problems.  It means that the Branch & Bound tree has exhausted all available main memory.  Your best immediate course of action is to se the Task Pane Engine tab MIP group Node File Start option to a low value such as 1 (for 1GB of memory),or even a fractional value.  This will cause the Gurobi Solver to write the Branch & Bound tree to a disk file (the “Node File”) once it reaches 1GB in size.  This should allow you to solve the problem, at some cost in extra solution time.  But it may be a good idea to upgrade your PC with more RAM to solve such problems.

Fiveleaper

A369130

seq=Table[GraphData[{"Fiveleaper",{n,n}},"DominationNumber"],{n,20}]

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

FoldedCube

Posisbly A122408?

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

GraphData["FoldedCube"]

Gear

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.7357&rep=rep1&type=pdf

Int. J. Contemp. Math. Sciences, Vol. 2, 2007, no. 24, 1193 - 1199
Domination in Jahangir Graph J2,m D. A. Mojdeh and A. N. Ghameshlou

(This is actually Gear)

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

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

Giraffe

A369133

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

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

Do[Print[{gn={"Giraffe",{n,n}},Flatten[{set=Flatten@FindDominatingSet[GiraffeGraph[n,n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,30}]

Grid m×n

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

http://arxiv.org/pdf/1102.5206v1.pdf

Wrong for n==6

From Chang and Clark (1993):

(correct), but:

(wrong).

gamma[n_,m_]:=
Piecewise[{
{Ceiling[m/3],n==1},
{Ceiling[(m+1)/2],n==2},
{Ceiling[(3m+1)/4],n==3},
{m+1,n==4&&(m==5||m==6||m==9)},
{m,n==4&&!(m==5||m==6||m==9)},
{Ceiling[(6m+4)/5]-1,n==5&&m==7},
{Ceiling[(6m+4)/5],n==5&&m≠7},
(* wrong
{Ceiling[(10m+4)/7],n==6},
*)
(* replace with Hare expression from Chang et al. 1993 *)
{m+Ceiling[(3m-2)/7],n==6&&Mod[m,7]==1},
{m+2+Ceiling[(3m-2)/7],n==6&&Mod[m,7]==3},
{m+1+Ceiling[(3m-2)/7],n==6&&!(Mod[m,7]==1||Mod[m,7]==3)},
{Ceiling[(5m+1)/3],n==7},
{Ceiling[(15m+7)/8],n==8},
{Ceiling[(23m+10)/11],n==9},
{Ceiling[(30m+15)/13]-1,n==10&&(Mod[n,13]==10||m==13||m==16)},
{Ceiling[(30m+15)/13],n==10&&Mod[n,13]!=10&&!(m==13||m==16)},
{Ceiling[(38m+22)/15]-1,n==11&&(m==11&&m==18||m==20||m==22||m==33)},
{Ceiling[(38m+22)/15],n==11&&!(m==11||m==18||m==20||m==22||m==33)},
{Ceiling[(80m+38)/29],n==12},
{Ceiling[(98m+54)/33]-1,n==13&&(Mod[m,33]==13||Mod[m,33]==16||Mod[m,33]==18||Mod[m,33]==19)},
{Ceiling[(98m+54)/33],n==13&&!(Mod[m,33]==13||Mod[m,33]==16||Mod[m,33]==18||Mod[m,33]==19)},
{Ceiling[(35m+20)/11]-1,n==14&&Mod[m,22]==7},
{Ceiling[(35m+20)/11],n==14&&Mod[m,22]!=7},
{Ceiling[(44m+28)/13]-1,n==15&&Mod[m,26]==5},
{Ceiling[(44m+28)/13],n==15&&Mod[m,26]!=5},
{Floor[(n+2)(m+2)/5]-4,n≥16}
}]

gamma[n,m]//TraditionalForm

DeleteCases[
{#1,#2,gamma@@#2,GraphData[#1,"DominationNumber"]}&@@@Select[{#,"Grid"/.GraphData[#,"NotationRules"]}&/@GraphData["Grid"],Length[#[[2]]]==2&],
{_,_,x_,x_}]

Grid n×n

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

A104519

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

Table[Piecewise[{{n,n≤4},{7,n==5},{10,n==6},{40,n==13}},Floor[(n+2)^2/5]-4],{n,51}]

FindSequenceFunction[seq,n-1]

Table[Piecewise[{{n,n≤4},{7,n==5},{10,n==6},{40,n==13}},Floor[(n+2)^2/5]-4],{n,23}]

Sufficient number of monominoes to exclude X-pentominoes from the n X n board

Index offset by 2

seq={1,2,3,4,7,10,12,16,20,24,29,35,40,47,53,60,68,76,84,92,101,111,121,131,141,152,164,176,188,200,213,227,241,255,269,284,300,316,332,348,365,383,401,419,437,456,476,496,516};

Length[l]

l2=Table[Piecewise[{{n-2,n≤6},{7,n==7},{10,n==8},{40,n==15}},Floor[n^2/5]-4],{n,3,51}]

l==l2

Table[{n,Piecewise[{{n,n≤4},{7,n==5},{10,n==6}},Floor[(n+2)^2/5]-4]},{n,20}]//Grid

Series[-x^3*(x^19-2*x^18+x^17-x^14+2*x^13-3*x^12+2*x^11+x^10-2*x^9+2*x^7-x^6-x^5+2*x^4+1)/((x-1)^3*(x^4+x^3+x^2+x+1)),{x,0,15}]

FullSimplify[SeriesCoefficient[-x^3*(x^19-2*x^18+x^17-x^14+2*x^13-3*x^12+2*x^11+x^10-2*x^9+2*x^7-x^6-x^5+2*x^4+1)/((x-1)^3*(x^4+x^3+x^2+x+1)),{x,0,n}],n∈Integers&&n>0]

Grid k×m×n

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

Grid n×n×n

A269706

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

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

FindSequenceFunction[DeleteMissing@seq,n]

FindGeneratingFunction[DeleteMissing@seq,x]

HalvedCube

Similar to A029866

Size of minimal covering code of length n and covering radius
1, 2, 2, 2, 4, 7, 12

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

Hamming (3, n)

A000982

seq=Table[GraphData[{"Hamming",{3,n}},"DominationNumber"],{n,2,7}]

Table[Ceiling[((n^2)/2)],{n,2,7}]

Hamming (4, n)

seq=Table[GraphData[{"Hamming",{4,n}},"DominationNumber"],{n,2,6}]

Hanoi

A122983

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

seq=Table[(2+(-1)^n+3^n)/4,{n,20}]

Table[Floor[3^n/4]+1,{n,0,20}]

Floor[3^Range[0,20]/4]+1

FindLinearRecurrence[seq]

LinearRecurrence[{3,1,-3},{1,1,3},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((1-3 (x^2))/(1-3 x-(x^2)+3 (x^3))),{x,0,20}],x]

Helm

seq=Table[GraphData[{"Helm",n},"DominationNumber"],{n,3,10}]

Table[-(x^n)+(1+x) (((x (2+x)))^n),{n,3,5}]//Expand

Exponent[-(x^n)+(1+x) (((x (2+x)))^n),x,Min]

Table[Exponent[-(x^n)+(1+x) (((x (2+x)))^n),x,Min],{n,3,10}]

HexagonalGrid n×n×n

3 * A000982(n).

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

Do[Print[{{"HexagonalGrid",{n,n,n}},{Length[set=FindDominatingSet[HexagonalGridGraph[{n,n,n}],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

seq={2,6,15,24,39,54,75,96,123,150,183,216,255,294,339,384,435,486,543,600};

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]

3Ceiling[Range[20]^2/2]

Table[3Ceiling[((n^2)/2)],{n,100}]

seq=Table[3/4 (1-(((-1))^n)+2 (n^2)),{n,100}]

StringTake[ToString[seq],{2,261}]

gf=x FindGeneratingFunction[seq,x]

StringReplace[ToString[gf,InputForm]," "->""]

CoefficientList[Series[-((3(1+(x^2)))/((((-1+x))^3) (1+x))),{x,0,20}],x]

FindLinearRecurrence[seq]

LinearRecurrence[{2,0,-2,1},{3,6,15,24,39},20]

Hypercube

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

Probably A000983

1, 2, 2, 4, 7, 12, 16, 32, 62 (next term not known)

Computed 1, 2, 2, 4, 7, 12, 16, 32, and took 62 from A000983

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

Jahangir

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.7357&rep=rep1&type=pdf

Int. J. Contemp. Math. Sciences, Vol. 2, 2007, no. 24, 1193 - 1199
Domination in Jahangir Graph J2,m D. A. Mojdeh and A. N. Ghameshlou

(This is actually Gear)

Keller

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

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

King m×n

DeleteCases[{#,mn="King"/.GraphData[#,"NotationRules"],Times@@(Floor[(#+2)/3]&/@mn),GraphData[#,"DominationNumber"]}&/@GraphData["King"],{_,_,x_,x_}]

King n×n

A075561

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

Table[Floor[(n+2)/3]^2,{n,10}]

Do[Print[{{"King",{n,n}},{Length[set=FindDominatingSet[KingGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

Kneser

k=Sort[{"Kneser"/.GraphData[#,"NotationRules"],GraphData[#,"DominationNumber"]}&/@GraphData["Kneser"]]

Cases[k,{{_,1},d_}:>d]

Cases[k,{{_,2},d_}:>d]

Cases[k,{{n_,3},d_}:>{n,d}]

Cases[k,{{n_,4},d_}:>{n,d}]

Knight m×n

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

TextGrid[Table[{n,GraphData[{"Knight",{n,n}},"DominatingSets"]/.{l_List:>First[l],Missing[_,l_List]:>l}},{n,2,20}],Dividers->All]//TraditionalForm

Table[GraphData[{"Knight",{n,n}},"DominationPolynomial"][x],{n,2,5}]

{#,"Knight"/.GraphData[#,"NotationRules"],GraphData[#,"DominationNumber"]}&/@GraphData["Knight"]

Knight n×n

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

A006075

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

Do[Print[{{"Knight",{n,n}},{Length[set=FindDominatingSet[KnightGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

Length[seq={1,4,4,4,5,8,10,12,14,16,21,24,28,32,36,40,46,52,57,62,68}]

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,5}]

FindGeneratingFunction[seq,x]//Head//Timing

Upper bounds for the terms after a(21) = 68 are as follows: 75, 82, 88, 96, 102, ... (see Frank Rubin's web site).

seq1={1,4,4,4,5,8,10,12,14,16,21,24,28,32,36,40,46,52,57,62,68,75,82,88,96,102};

Do[Print[{k,FindSequenceFunction[Drop[seq1,k],n-k]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindLinearRecurrence[Drop[seq1,k]]//Head//Timing}],{k,0,5}]

FindGeneratingFunction[seq1,x]//Head//Timing

Ladder

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

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

Table[1+Floor[n/2],{n,20}]

LadderRung

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

LucasCube

A364653

seq=Table[GraphData[{"LucasCube",n},"DominationNumber"],{n,15}]

Ilic, A. and Milosevic, M.  "The Parameters of Fibonacci and Lucas Cubes."  Ars Math. Contemp. 12, 25–29, 2017.

Do[Print[{gn={"LucasCube",n},Flatten[{set=Flatten@FindDominatingSet[LucasCubeGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,12}]

Do[Print[{gn={"LucasCube",n},Flatten[{set=Flatten@FindDominatingSet[LucasCubeGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,{12}}]

MengerSponge

A306244

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

MoebiusLadder

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

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

Table[Floor[(n+1)/4]+Ceiling[(n+1)/4],{n,3,20}]

FullSimplify[(1/2) (1+n+Cos[((n π)/2)])-(Floor[(n+1)/4]+Ceiling[(n+1)/4]),n∈Integers]

Mycielski

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

Computed as n-1 for n <10; inferred beyond that

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

Table[DominationNumber[MycielskiGraph[n]],{n,8}]//Timing

Odd

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

A296852

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

Do[Print[{gn={"Odd",n},Flatten[{set=Flatten@FindDominatingSet[OddGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,5}]

Pan

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

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

Path

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

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

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

Pell

seq=Table[GraphData[{"Pell",n},"DominationNumber"],{n,0,9}]

Do[Print[{gn={"Pell",n},Flatten[{set=Flatten@FindDominatingSet[PellGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,7}]

Do[Print[{gn={"Pell",n},Flatten[{set=Flatten@FindDominatingSet[PellGraph[n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,{7}}]

Prism

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

A004524

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

Table[DominationNumber[PrismGraph[n]],{n,3,50}]//Timing

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

Queen m×n

{#,"Queen"/.GraphData[#,"NotationRules"],GraphData[#,"DominationNumber"]}&/@GraphData["Queen"]

Queen n×n

A075458

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

Do[Print[{{"Queen",{n,n}},{Length[set=FindDominatingSet[QueenGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

Length[seq={1,1,1,2,3,3,4,5,5,5,5,6,7,8,9,9,9,9,10,11,11,12,12,13,13}]

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,5}]

FindGeneratingFunction[seq,x]//Head//Timing

a(n) = p or p+1, where p = ceiling(n/2), proved for all n <= 132, except n = 3, 11.

diff=MapIndexed[#-Ceiling[#2[[1]]/2]&,seq]

A344001:

Position[diff,1]//Flatten

A344000 (for 12 and up):

Position[diff,0]//Flatten

Rook m×n

DeleteCases[{#,GraphData[#,"DominationNumber"],Min@@("Rook"/.GraphData[#,"NotationRules"])}&/@GraphData["Rook"],{_,x_,x_}]

Rook n×n

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

RookComplement n×n

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

Do[Print[{{"RookComplement",{n,n}},{Length[set=FindDominatingSet[GraphComplement@RookGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

SierpinskiCarpet

A291775

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

seq={3,18,130,1026};

gf=x FindGeneratingFunction[seq,x,ValidationLength->2]

SierpinskiGasket

Teguia, A.~M. and Godbole, A.~P.  "Sierpńiski Gasket Graphs and Some of Their Properties."  Australasian J. Combin. 35, 181–192, 2006.

A000244(n-2) for n > 2

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

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

Do[Print[{{"SierpinskiSieve",n},{Length[set=FindDominatingSet[SierpinskiSieveGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,8}]

seq={1,2,3,9,27,81,243,729};

gf=x FindGeneratingFunction[seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>0]

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

SierpinskiTetrahedron

A002023(n-3) for n > 2

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

Do[Print[{{"SierpinskiTetrahedron",n},{Length[set=FindDominatingSet[SierpinskiTetrahedronGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,7}]

seq={1,2,6,24,96,384,1536};

gf=x FindGeneratingFunction[seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>0]

Table[3 (2^(2n-5)),{n,8}]

Star

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

Table[GraphData[{"Star",n},"DominationNumber"],{n,20}]

seq=Table[GraphData[{"Star",n},"DominationNumber"],{n,3,20}]

Sun

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

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

Sunlet

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

Tetrahedral

A347782

seq=Table[GraphData[{"Tetrahedral",n},"DominationNumber"],{n,6,12}]

Do[Print[{{"Tetrahedral",n},{Length[set=FindDominatingSet[TetrahedralGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,6,19}]

seq={2,4,5,7,8,10,11,13,14,18,19,23,24,29};

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,4}]

FindGeneratingFunction[seq,x]//Head//Timing

TorusGrid n×n

A094087

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

FindGeneratingFunction[seq,x]//Head//Timing

seq=Cases[Import["https://oeis.org/A094087/b094087.txt","Table"],{_Integer,a_}:>a]

FindGeneratingFunction[seq,x]//Head//Timing

a(5n) = 5n^2.

it is conjectured that a(5n-1) = 5*n^2 - n
a(5n+1) = 5n^2 + 4n - 1 for n >= 1.

(5n^2-n/.Solve[5n-1==k,n]//Simplify)/.k->n

(5n^2+4n-1/.Solve[5n+1==k,n]//Simplify)/.k->n

Table[Piecewise[{{5(n/5)^2,Mod[n,5]==0},{(1/5) n (1+n),Mod[n,5]==4},{(1/5) (-8+2 n+(n^2)),Mod[n,5]==1}},XXX],{n,20}]

Table[Print[{gn={"TorusGrid",{n,n}},Flatten@FindDominatingSet[GraphData[gn],Method->"MOSEK"]//Timing}],{n,3,20}]

Transposition

A347790

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

but Stan notes Pratt obtained bounds on Transposition(6) of [55, 66] (2016-03-03)

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

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

Table[DominationNumber[TranspositionGraph[n]],{n,5}]//Timing

Do[Print[{{"Transposition",n},{Length[set=FindDominatingSet[TranspositionGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,6}]

seq={1,1,2,4,15};

Trapezohedron

A007395

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

Triangular

seq=Table[GraphData[{"Triangular",n},"DominationNumber"],{n,5,20}]

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

TriangularHoneycombAcuteKnight

A289903

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

Do[Print[{{"TriangularHoneycombAcuteKnight",n},{Length[set=FindDominatingSet[TriangularHoneycombAcuteKnightGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,30}]

Length[seq={1,3,3,3,3,6,9,9,9,10,15,18,18,18,21,28,30,30,34,36,45,45,48,51,55,63,63,70,75,78,84,90,96,100,105,111,118,123,132,136,144,150,157,165,171,178,186,195,202,210,219,226,234,243,253,261,270,280,288,297,307,318,330,337,348,357,370}]

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,20}]

FindGeneratingFunction[seq,x]//Head//Timing

TriangularHoneycombBishop

A110654

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

Do[Print[{{"TriangularHoneycombBishop",n},{Length[set=FindDominatingSet[TriangularHoneycombBishopGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,30}]

Table[Ceiling[n/2],{n,10}]

TriangularHoneycombObtuseKnight

A251534

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

Do[Print[{{"TriangularHoneycombObtuseKnight",n},{Length[set=FindDominatingSet[TriangularHoneycombObtuseKnightGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,21,25}]

seq={1,3,6,4,5,5,6,6,9,11,12,14,15,16,18,19,23,25,27,30,31,33,36,39,42,45};

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

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,6}]

FindGeneratingFunction[seq,x]//Head//Timing

TriangularHoneycombQueen

A229803

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"DominationNumber"],{n,20}]

Length[seq]

seq=OEISBFile[229803]

Length[seq]

FindSequenceFunction[seq,n]//InputForm

FindGeneratingFunction[seq,x]//Head//Timing

Do[Print[{{"TriangularHoneycombQueen",n},{Length[set=FindDominatingSet[TriangularHoneycombQueenGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

TriangularHoneycombRook

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

Web

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

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

Wheel

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

seq=Table[GraphData[{"Star",n},"DominationNumber"],{n,4,20}]

FindSequenceFunction[seq,n-3]

WhiteBishop n×n

A004524

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

Table[Floor[(n+1)/4]+Floor[(n+2)/4],{n,2,10}]

Do[Print[{{"WhiteBishop",{n,n}},{Length[set=FindDominatingSet[WhiteBishopGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,2,50}]

Zebra n×n

A369131

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

FindGeneratingFunction[seq,x]//Head//Timing

Do[Print[{gn={"Zebra",{n,n}},Flatten[{set=Flatten@FindDominatingSet[ZebraGraph[n,n],Method->"MOSEK"],Length[set]}//Timing,1]}],{n,30}]