Total Domination Number

Author

Eric W. Weisstein
February 9, 2024

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

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

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

Figure

GraphicsRow[HighlightGraph[GraphData["P","Graph","Labeled"],#2,PlotLabel->Style[#1,Directive[Black,Italic,FontFamily->"Times"]],VertexSize->Medium]&@@@Transpose[{
{"dominating set","total dominating set"},
Replace[GraphData["P",{"DominatingSets","TotalDominatingSets"}],{l_List:>l[[1]],Missing[_,l_]:>l},{1}]
}]]

Theorems

Diameter 2, Girth 5

Henning and Yeo 2013, Theorem 14.7, p. 121

SortBy[Select[GraphData[All],GraphData[#,"Diameter"]==2&&GraphData[#,"Girth"]==5&],GraphData[#,"V"]&]

Print[{#,1+Sqrt[GraphData[#,"V"]-1],Length[set=TotalDominatingSet[GraphData[#]]],set}]&/@%;

γ≤(Subscript[γ, t])≤2γ

For a graph with no isolated vertex

Henning and Yeo 2013, Theorem 2.25, p. 17

Select[Intersection@@(GraphData[#,"Defined"]&/@{"DominationNumber","TotalDominationNumber"}),
!(1≤GraphData[#,"TotalDominationNumber"]/GraphData[#,"DominationNumber"]≤2)&]

(Subscript[γ, t])≤(n+l)/2

For a tree with n>=2 vertices and l leaves

Henning and Yeo 2013, Theorem 4.2, p. 31

Select[
Intersection[GraphData["Tree"],GraphData["TotalDominationNumber","Defined"]],
GraphData[#,"TotalDominationNumber"]>(GraphData[#,"V"]+GraphData[#,"LeafCount"])/2&]

Planar with diam==2, then (Subscript[γ, t])≤3

Henning and Yeo 2013, Theorem 6.3, p. 56

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

Missing

DateString[]

Grid[missing=Cases[Sort[GraphData[#,{"V","TotalDominationNumber","#"}]&/@GraphData[All]],{v_,Missing["NotAvailable"],g_}:>{v,g}],Alignment->{{Decimal,Left}},Dividers->All]

Length[missing]

Export[file="/Users/eww/Documents/Mathematica/Paclets/GraphData/Data/ForPratt/TotalDominationNumber.tsv",{GraphNameToPrattName[#2],#1,GraphData[#2,"M"]}&@@@missing]

Parametrized family table

GraphDataCountTable["TotalDominationNumber",Join[{"Antiprism"->302255,"Apollonian"->302487,"Bishop"->063224,"BlackBishop"->004523,"Centipede"->254667,"Crown"->010709,"CrossedPrism"->005843,"CubeConnectedCycle"->302489,"Cycle"->004524,"DiagonalIntersection"->302400,"DorogovtsevGoltsevMendes"->067771,"FibonacciCube"->291294,"FoldedCube"->302613,"Gear"->004526,{"Grid",2}->302488,{"Grid",3}->302508,"HalvedCube"->303846,"Hanoi"->034472,"Helm"->000027,
"HexagonalGrid"->046092(* probably *),
"Hypercube"->247181,"Keller"->010709,"King"->302401,"Knight"->261752,"Ladder"->302402,"LadderRung"->005843,"LucasCube"->365090,"MoebiusLadder"->302404,"Mycielski"->000027,"Pan"->004524,"Pasechnik"->010722,"Path"->004524,"Pell"->365091,"Prism"->302405,"Queen"->303003,"Rook"->000027,"SierpinskiCarpet"->347651,"Sun"->004526,"Sunlet"->000027,"TorusGrid"->302406,"Transposition"->303150,"Triangular"->004523,"TriangularGrid"->302486,"TriangularHoneycombAcuteKnight"->342373,"TriangularHoneycombBishop"->004523,"TriangularHoneycombObtuseKnight"->342374,"TriangularHoneycombQueen"->004526,
"TriangularSnake"->004523, (* for n > 3 *)
"Web"->000027,"WhiteBishop"->004523},Thread[{"Barbell","Book","CocktailParty","Complete","CompleteBipartite","CompleteTripartite","Dipyramid","PathComplement","Star","Wheel"}->007395]]]

Parametrized familes

<<MathWorld`Graphs`

AlternatingGroup

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

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"TotalDominationNumber"],{n,20}]

Antelope n×n

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

Antiprism

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

A302255

seq=Table[GraphData[{"Antiprism",n},"TotalDominationNumber"],{n,k=3,kmax=25}]

(seq=Table[Length@TotalDominatingSet[AntiprismGraph[n]],{n,3,25}])//Timing

coef=FindLinearRecurrence[seq]

seq=LinearRecurrence[{1,0,0,0,0,0,1,-1},{1,2,2,3,4,4,4,5,6,6},{0,100}]

init=Table[a[k]==seq[[k]],{k,8}]

RSolve[Prepend[init,a[n]==a[n-1]+a[n-7]-a[n-8]],a[n],n]

gf=FindGeneratingFunction[seq,x]

InputForm[gf]

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

soln=Refine[SeriesCoefficient[gf,{x,0,n}],n≥0]

soln=((((-1))^(1+((2 n)/7))) (-12+16 (((-1))^(1/7))-18 (((-1))^(2/7))+18 (((-1))^(3/7))-16 (((-1))^(4/7))+12 (((-1))^(5/7))-13 (((-1))^(6/7))-28 (((-1))^(2 n/7))-28 (((-1))^((2 (1+n))/7))-5 (((-1))^((4 (1+n))/7))-31 (((-1))^((2 (2+n))/7))-30 (((-1))^((2 (3+n))/7))+32 (((-1))^((1/7) (1+2 n)))-5 (((-1))^((2/7) (1+2 n)))+30 (((-1))^((1/7) (3+2 n)))+31 (((-1))^((1/7) (5+2 n)))+4 (((-1))^((1/7) (1+4 n)))+3 (((-1))^((1/7) (3+4 n)))+4 (((-1))^((1/7) (5+4 n))))+(-16+12 (((-1))^(1/7))-13 (((-1))^(2/7))+12 (((-1))^(3/7))-16 (((-1))^(4/7))+18 (((-1))^(5/7))-18 (((-1))^(6/7))) (E^(-(2/7) I n π))+(-32+28 (((-1))^(1/7))-30 (((-1))^(2/7))+31 (((-1))^(3/7))-31 (((-1))^(4/7))+30 (((-1))^(5/7))-28 (((-1))^(6/7))) (E^(-(4/7) I n π))+(-4+4 (((-1))^(3/7))-5 (((-1))^(4/7))+3 (((-1))^(5/7))-5 (((-1))^(6/7))) (E^(-(6/7) I n π)))/(7 (3+3 (((-1))^(1/7))-2 (((-1))^(2/7))+(((-1))^(3/7))-(((-1))^(5/7))+2 (((-1))^(6/7))))+((4 (1+n))/7);

FullSimplify[soln,n∈Integers]

FullSimplify[RootReduce[soln],n∈Integers]

Table[(1/7) (4+4 n+(E^((4 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,1]+(E^(-(4/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,2]+(E^(-(2/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,3]+(E^((2 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,4]+(E^(-(6/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,5]+(E^((6 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,6]),{n,0,5}]//RootReduce

{4,-4,-2,2,-6,6}

FullSimplify[FindSequenceFunction[Join@@Table[{4,-4,-2,2,-6,6},{10}],k],k∈Integers]

Table[(1/6) (8 (((-1))^n)+9 Cos[((n π)/3)]+6 Cos[((2 n π)/3)]+6 Cos[((4 n π)/3)]+8 Cos[((5 n π)/3)]-2 Cos[(1/3) (1+n) π]+(Sqrt[3]) (Sin[((n π)/3)]+8 Sin[((2 n π)/3)]-8 Sin[((4 n π)/3)]-2 Sin[((5 n π)/3)])),{n,6}]

Sum[Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,k]Exp[{4,-4,-2,2,-6,6}[[k]] n Pi I/7],{k,6}]

Sum[Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,k]Exp[(1/6) (8 (((-1))^k)+9 Cos[((k π)/3)]+6 Cos[((2 k π)/3)]+6 Cos[((4 k π)/3)]+8 Cos[((5 k π)/3)]-2 Cos[(1/3) (1+k) π]+(Sqrt[3]) (Sin[((k π)/3)]+8 Sin[((2 k π)/3)]-8 Sin[((4 k π)/3)]-2 Sin[((5 k π)/3)])) n Pi I/7],{k,6}]

sum=Sum[Root[1+7 ((#)^2)+28 ((#)^3)+42 ((#)^4)+28 ((#)^5)+7 ((#)^6)&,k]Exp[{4,-4,-2,2,-6,6}[[k]] n Pi I/7],{k,6}];

Table[(4+4n+sum)/7,{n,0,30}]//FullSimplify

FullSimplify[RootReduce[Expand[ExpToTrig[soln]]]]

Table[(1/7) (4+4 n+(E^((4 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,1]+(E^(-(4/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,2]+(E^(-(2/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,3]+(E^((2 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,4]+(E^(-(6/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,5]+(E^((6 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,6]),{n,3,10}]

a[n_]:=(1/7) (4+4 n+(E^((4 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,1]+(E^(-(4/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,2]+(E^(-(2/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,3]+(E^((2 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,4]+(E^(-(6/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,5]+(E^((6 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,6])

Table[FullSimplify[a[n]-a[n-7k],n∈Integers],{k,10}]

FullSimplify[a[n]-a[n-7k],(n|k)∈Integers]

FullSimplify[a[n],Mod[n,7]==0]

Table[(4+4 n+(E^((4 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,1]+(E^(-(4/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,2]+(E^(-(2/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,3]+(E^((2 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,4]+(E^(-(6/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,5]+(E^((6 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,6])/7,{n,20}]//RootReduce

Table[(4+4 n+E^(4 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,1]+E^(-4 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,2]+E^(-2 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,3]+E^(2 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,4]+E^(-6 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,5]+E^(6 I n Pi/7) Root[1+7 #1^2+28 #1^3+42 #1^4+28 #1^5+7 #1^6&,6])/7,{n,20}]//RootReduce

a[n_]:=(1/7) (4+4 n+(E^((4 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,1]+(E^(-(4/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,2]+(E^(-(2/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,3]+(E^((2 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,4]+(E^(-(6/7) I n π)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,5]+(E^((6 I n π)/7)) Root[1+7 ((#1)^2)+28 ((#1)^3)+42 ((#1)^4)+28 ((#1)^5)+7 ((#1)^6)&,6])

Apollonian

A302487

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

Do[Print[{{"Apollonian",n},{Length[set=TotalDominatingSet[ApollonianGraph[n]]],set}//Timing}],{n,9}]

seq={2,2,3,4,7,16,43,64,67,70,70};

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

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

Barbell

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

Bishop n×n

A063224(n) for n > 2

seq=Table[GraphData[{"Bishop",{n,n}},"TotalDominationNumber"],{n,20}]

2Floor[2Range[20]/3]

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

GraphicsGrid[Partition[Table[HighlightGraph[GraphData[{"Bishop",{n,n}},"Graph","Grid"][[1]],GraphData[{"Bishop",{n,n}},"TotalDominatingSets"]/.{l_List:>l[[1]],Missing[_,l_]:>l},LabelStyle->Directive[Black,FontFamily->"Times"],PlotLabel->Row[{Style["n",Italic]," == ",n}],VertexSize->{"Scaled",.02}],{n,2,10}],UpTo[4]],ImageSize->1000,PlotLabel->"minimum total dominating configurations for n×n bishop graphs"]

Do[Print[{{"Bishop",{n,n}},{Length[set=FindTotalDominatingSet[BishopGraph[n,n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,2,22}]

seq={2,4,4,6,8,8,10,12,12,14,16,16,18,20,20,22,24,24,26,28};

FindLinearRecurrence[Drop[seq,2]]

seq=LinearRecurrence[{1,0,1,-1},{0,2,4,4},100]

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

Length[seq]

FindSequenceFunction[seq,n]

InputForm[%]

Solve[-6-4*\[FormalN]+\[FormalY][\[FormalN]]+\[FormalY][1+\[FormalN]]+\[FormalY][2+\[FormalN]]==0/.\[FormalN]->n-2,\[FormalY][n] ]

Clear[y];
y[1]=0;
y[2]=y[3]=y[4]=4;
y[n_]:=y[n]=4n-6-y[n-1]-y[n-2]

Array[y,21]-seq

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[gf/x,{x,0,20}],x]-seq

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

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

seq1=Table[(2/3) (-1+2 n+ChebyshevU[n,-(1/2)]),{n,50}]

seq2=Table[(2/9) (-9+6(n+1)+2 (Sqrt[3]) Sin[((2 (n+1) π)/3)]),{n,50}]

seq1-seq2

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

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

Table[With[{m=n-1},m+Floor[m/3]+Mod[m,3]],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"TotalDominationNumber"],{n,20}]

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

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

seq={2,2,3,4,4,5,6,6,7,8,8,9,10,10,11,12,12,13};

gf=FindGeneratingFunction[seq,x]

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

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

Book

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

Bruhat

Matches A003422 up to n==5

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"TotalDominationNumber"],
2},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

Table[GraphData[{"CompleteTripartite",{k,m,n}},"TotalDominationNumber"],{n,5},{m,n},{k,m}]//Column

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"TotalDominationNumber"],
2
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

CrossedPrism

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

FindSequenceFunction[seq,n-1]

Crown

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

CubeConnectedCycle

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

A302489

Do[Print[{{"CubeConnectedCycle",n},{Length[set=FindTotalDominatingSet[CubeConnectedCycleGraph[n]]//Flatten],set}//Timing}],{n,3,7}]

data={{{"CubeConnectedCycle",3},{2,5,8,10,15,16,18,20}},{{"CubeConnectedCycle",4},{3,5,10,12,14,16,18,22,23,28,29,30,32,35,42,45,46,49,55,56,59,60,61,63}},{{"CubeConnectedCycle",5},{2,5,7,12,14,15,20,23,28,32,36,37,39,40,41,45,47,51,55,56,57,58,68,69,70,73,75,76,77,83,85,87,95,97,98,104,107,109,110,112,115,116,124,125,127,129,133,135,138,140,145,151,155,156,157,159}},{{"CubeConnectedCycle",6},{1,3,8,10,16,17,19,25,26,27,32,38,39,44,46,50,51,56,57,59,60,64,68,69,76,77,82,83,89,91,92,95,102,105,107,115,116,121,124,127,132,133,135,138,139,145,147,148,152,153,157,161,163,167,171,172,177,178,180,183,185,187,191,196,201,202,204,212,214,215,219,220,227,228,230,235,241,242,243,247,249,252,254,260,262,265,266,268,270,276,278,280,281,286,291,293,296,297,304,306,310,311,312,313,314,317,319,320,321,327,328,331,332,336,337,338,344,346,351,352,363,364,367,371,374,380,381,382}}};

TotalDominatingSetQ[CubeConnectedCycleGraph[#[[2]]],#2]&@@@data

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

Cycle

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

A004524

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

seq=Table[GraphTotalDominationNumber[CycleGraph[n]],{n,3,20}]

FindSequenceFunction[seq,n-2]

Henning and Yeo 2013, p. 14

seq=Table[Floor[n/2]+Ceiling[n/4]-Floor[n/4],{n,3,30}]

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

Table[(1/2) (1+n-Cos[((n π)/2)]),{n,3,20}]

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

And@@Equal@@@Table[{
Floor[(n+2)/4]+Floor[(n+3)/4],
(1/2) (1+n-Cos[((n π)/2)]),
Floor[n/2]+Ceiling[n/4]-Floor[n/4]
},{n,1000}]

Subtract@@@Table[{Floor[n/2]+Ceiling[n/4]-Floor[n/4],(1/2) (1+n-Cos[((n π)/2)])},{n,100}]//Union

Length/@Table[TotalDominatingSet[CycleGraph[n]],{n,3,30}]

Table[Floor[n/2-1]+Ceiling[n/4-1/2]-Floor[n/4-1/2],{n,0,20}]

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

DiagonalIntersection

A302400

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

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindGeneratingFunction[DeleteMissing@seq,x]//Head

DorogovtsevGoltsevMendes

A067771

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

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

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

FindLinearRecurrence[%]

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

Table[3/2((3^(n-3))+1),{n,0,10}]

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

DoubleCone

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

Empty

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

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

FibonacciCube

A291294

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

Compute:

seq={2,2,2,3,5,7,10,13,20,30,44,65};

FindSequenceFunction[DeleteMissing@seq,n-1]

Fiveleaper n×n

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

FoldedCube

A302613

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

Gear

A004526

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

FindSequenceFunction[seq,n-2]//FullSimplify

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

Grid m×n

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

A300358

Henning and Yeo 2013, pp. 106-107:

Table[GraphData[{"Grid",{m,n}},"TotalDominationNumber"],{n,10},{m,n}]//Column

data=Import["https://oeis.org/A300358/b300358.txt","Table"][[All,2]]

Quiet@Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]/._Part:>Missing["NotAvailable"]//Column//TraditionalForm

2×n

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{2,n}]],{n,10}])//Timing

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

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

3×n

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{3,n}]],{n,2,15}])//Timing

Simplify[FindSequenceFunction[seq,n-1],n∈Integers]

4×n

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{4,n}]],{n,20}])//Timing

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

SeriesCoefficient[x FindGeneratingFunction[seq,x],{x,0,n}]

FullSimplify[%,n∈Integers&&n>0]

5×n

eps[{a_,b_},n_]:=Boole[Mod[n,b]==a]

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{5,n}]],{n,20}])//Timing

Table[Ceiling[(3n+2)/2]+eps[{0,4},n],{n,20}]

SeriesCoefficient[x FindGeneratingFunction[seq,x],{x,0,n}]

FullSimplify[%,n∈Integers&&n>0]

6×n

eps[{a_,b_},n_]:=Boole[Mod[n,b]==a]

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{6,n}]],{n,30}])//Timing

Table[2Ceiling[(6n+6)/7]-2eps[{4,7},n],{n,20}]

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

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

FullSimplify[%,n∈Integers&&n>0]

7×n

eps[{a_,b_},n_]:=Boole[Mod[n,b]==a]

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{7,n}]],{n,30}])//Timing

Table[2n+2-eps[{1,2},n],{n,20}]

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

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

FullSimplify[%,n∈Integers&&n>0]

8×n

eps[{a_,b_},n_]:=Boole[Mod[n,b]==a]

(seq=Table[Length@TotalDominatingSet[System`GridGraph[{8,n}]],{n,30}])//Timing

Table[2Ceiling[(10n+10)/9]-2eps[{1,9},n]+2eps[{7,9},n],{n,20}]

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

SeriesCoefficient[x {x,0,n}]

FullSimplify[%,n∈Integers&&n>0]

Grid n×n

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

A302488

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

seq={2,3,6,9,12,15,20,25,30,35,42,49,56,63,72,81,90,99,110,121,132,143,156,169,182,195,210,225,240};

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

seq=Table[((((-1))^n)+2 n (2+n)+4 Sin[((n π)/2)]-1)/8,{n,70}]

FindLinearRecurrence[seq]

LinearRecurrence[{2,-1,0,1,-2,1},{1,2,3,6,9,12},20]

gf=FindGeneratingFunction[seq,x]

InputForm[gf]

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

Grid k×m×n

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

Table[GraphData[{"Grid",{k,m,n}},"TotalDominationNumber"],{n,5},{m,n},{k,m}]//Column

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"TotalDominationNumber"],
Piecewise[{{Missing["NotApplicable"],k m n==1||k m n==2}},2(k+m+n-3)]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

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

A302508

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

FindSequenceFunction[DeleteMissing@seq,n-1]//Head//Timing

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

Do[Print[{{"Grid",{n,n,n}},{Length[set=TotalDominatingSet[System`GridGraph[{n,n,n}]]],set}//Timing}],{n,7}]

HalvedCube

A303846

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

Do[Print[{{"HalvedCube",n},{Length[set=FindTotalDominatingSet[HalvedCubeGraph[n]]//Flatten],set}//Timing}],{n,10}]

data={{{"HalvedCube",1},{0.03125`,{0,{1}}}},{{"HalvedCube",2},{0.`,{2,{1,2}}}},{{"HalvedCube",3},{0.015625`,{2,{1,3}}}},{{"HalvedCube",4},{0.65625`,{2,{1,2}}}},{{"HalvedCube",5},{1.140625`,{3,{1,2,13}}}},{{"HalvedCube",6},{1.109375`,{4,{1,2,15,16}}}},{{"HalvedCube",7},{3.328125`,{4,{1,11,56,62}}}},{{"HalvedCube",8},{652.3125`,{8,{3,30,33,64,65,96,99,126}}}},{{"HalvedCube",9},{937168.078125`,{12,{37,39,55,105,121,123,140,146,158,196,208,214}}}}};

Length/@data[[All,2,2,2]]

TotalDominatingSetQ[HalvedCubeGraph[#1[[2]]],#2[[2,2]]]&@@@data

FindSequenceFunction[Rest@seq,n+1]//Head//Timing

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

Hamming(3, n)

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

Hamming(4, n)

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

Hanoi

Looks like A034472

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

FindSequenceFunction[seq,n]//FullSimplify

Helm

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

FindSequenceFunction[seq,n-2]

Hypercube

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

A247181

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

Keller

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

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

Do[Print[{{"Keller",n},{Length[set=TotalDominatingSet[KellerGraph[n]]],set}//Timing}],{n,4}]

GraphData[{"Keller",4},"TotalDominatingSets"]

King m×n

A303378

Table[GraphData[{"King",{m,n}},"TotalDominationNumber"],{n,10},{m,n}]//Column

data=Import["https://oeis.org/A303378/b303378.txt","Table"][[2;;,2]]

Quiet@Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]/._Part:>Missing["NotAvailable"]//Column//TraditionalForm

King n×n

A302401

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

GraphicsGrid[Partition[Table[HighlightGraph[GraphData[{"King",{n,n}},"Graph","Grid"][[1]],GraphData[{"King",{n,n}},"TotalDominatingSets"]/.{l_List:>l[[1]],Missing[_,l_]:>l},LabelStyle->Directive[Black,FontFamily->"Times"],PlotLabel->Row[{Style["n",Italic]," == ",n}],VertexSize->{"Scaled",.02}],{n,2,10}],UpTo[4]],ImageSize->1000,PlotLabel->"minimum total dominating configurations for n×n king graphs"]

Built-in (COIN)

Do[Print[{{"King",{n,n}},{Length[set=TotalDominatingSet[KingGraph[n,n]]],set}//Timing}],{n,17}]

data={{{"King",{2,2}},{3,4}},{{"King",{3,3}},{5,6}},{{"King",{4,4}},{3,6,9,11}},{{"King",{5,5}},{7,9,13,17,19}},{{"King",{6,6}},{1,8,11,18,20,26,29,35}},{{"King",{7,7}},{3,9,13,19,20,30,37,40,41}},{{"King",{8,8}},{10,11,14,15,26,30,35,39,50,51,54,63}},{{"King",{9,9}},{3,11,13,16,17,38,39,42,43,44,57,65,67,70,71}},{{"King",{10,10}},{9,12,13,16,20,27,42,43,46,50,57,59,72,75,82,85,88,89}},{{"King",{11,11}},{13,14,17,18,21,31,46,47,50,54,62,65,79,81,91,95,98,101,103,106,109}},{{"King",{12,12}},{14,15,18,19,22,23,50,51,54,55,58,59,86,87,90,91,94,95,122,123,126,127,130,131}},{{"King",{13,13}},{15,16,19,22,25,32,35,38,54,55,71,73,76,77,85,93,94,97,99,115,116,132,135,138,145,148,151,154,155}},{{"King",{14,14}},{16,19,20,23,26,27,30,36,61,66,69,72,76,79,83,87,110,113,118,121,125,128,131,136,161,167,170,171,174,177,178,181}},{{"King",{15,15}},{17,18,21,24,25,28,29,35,62,67,70,71,74,78,81,89,107,114,115,118,123,126,134,141,152,153,159,160,163,179,186,197,198,201,204,205,208,224}},{{"King",{16,16}},{18,19,22,23,26,27,30,31,66,67,70,71,74,75,78,79,114,117,118,121,123,126,127,130,138,163,166,167,172,175,178,184,187,191,213,222,226,227,230,233,234,237,239}},{{"King",{17,17}},{6,19,20,24,27,30,33,43,46,50,57,70,73,81,87,94,97,101,110,118,124,128,132,138,142,148,156,169,179,185,188,193,196,199,203,206,209,217,245,248,254,257,258,261,264,267,268,271}}};

TotalDominatingSetQ[KingGraph@@#[[2]],#2]&@@@data

And@@%

Length/@data[[All,2]]

"Gurobi"

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

Recognize

seq={0,2,2,4,5,8,9,12,15,18,21,24,29,32,38,43,48,53,60,66,72,79};

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

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

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

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

Knight m×n

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

Knight n×n

A261752

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

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

Do[Print[{{"Knight",{n,n}},{Length[set=TotalDominatingSet[KnightGraph[n,n]]],set}//Timing}],{n,15}]

seq={6,7,8,10,14,18,22,25,28,32,36,43,48,54,58,66,70,78,84,91,98,107,112,123,128,139,146};

FindLinearRecurrence[seq]//Head//Timing

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

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

Ladder

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

A302402

Henning and Yeo 2013, pp. 106-107:

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

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

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

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

seq=Table[(2/9) (3+3 n-3 Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((2 n π)/3)]),{n,0,70}]

FindLinearRecurrence[seq]

LinearRecurrence[{1,0,1,-1},{2,2,2,4},{0,20}]

Table[Length[TotalDominatingSet[LadderGraph[n]]],{n,40}]==Rest@seq

gf=FindGeneratingFunction[seq,x]

InputForm[gf]

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

LadderRung

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

FindSequenceFunction[seq,n]

LucasCube

A365090

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

Do[Print[With[{gn={"LucasCube",n}},{gn,{Length[set=Flatten@FindTotalDominatingSet[GraphData[gn],Method->"MOSEK"]],set}//Timing}]],{n,15}]

MengerSponge

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

MoebiusLadder

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

A302404

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

FindLinearRecurrence[seq]

seq=LinearRecurrence[{1,0,0,0,0,1,-1},{2,3,4,4,6,6,6,7},{-2,30}]

seq=LinearRecurrence[{1,0,0,0,0,1,-1},{2,2,2,3,4,4,6,6},{0,80}]

gf=FindGeneratingFunction[seq,x]

InputForm[gf]

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

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

FullSimplify[%,n∈Integers]

Table[ (3-(((-1))^n)+4 n+Cos[((n π)/3)]-3 Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((n π)/3)]+((Sin[((2 n π)/3)])/(Sqrt[3])))/6,{n,0,20}]

a[n_]:=(1/6) (3+(((-1))^(1+n))+4 n+Cos[((n π)/3)]-3 Cos[((2 n π)/3)]+(Sqrt[3]) Sin[((n π)/3)]+((Sin[((2 n π)/3)])/(Sqrt[3])))

FullSimplify[a[n]-a[n-6k],(n|k)∈Integers]

Mycielski

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

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

Do[Print[{{"Mycielski",n},{Length[set=TotalDominatingSet[MycielskiGraph1[n]]],set}//Timing}],{n,11}]

Odd

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

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

Do[Print[{{"Odd",n},{Length[set=TotalDominatingSet[OddGraph1[n]]],set}//Timing}],{n,7}]

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

Pan

A004524

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

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

FullSimplify[FindSequenceFunction[{0,0,1,2,2,2,3,4,4,4,5,6,6,6,7,8,8,8,9,10,10,10,11},n],n∈Integers]

seq=Table[(n+Cos[((n π)/2)]-1)/2,{n,0,30}]

FindLinearRecurrence[seq]

LinearRecurrence[{2,-2,2,-1},{0,0,1,2},{0,20}]

FindGeneratingFunction[seq,x]

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

Path

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

A004524

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

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

Table[Floor[n/2]+Ceiling[n/4]-Floor[n/4],{n,30}]

Henning and Yeo 2013, p. 14

PathComplement

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

Pell

A365091

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

Do[Print[With[{gn={"Pell",n}},{gn,{Length[set=Flatten@FindTotalDominatingSet[GraphData[gn],Method->"MOSEK"]],set}//Timing}]],{n,0,9}]

Prism

A302405

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

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

FindLinearRecurrence[seq]

seq=LinearRecurrence[{1,0,0,0,0,1,-1},{2,4,4,4,5,6,6,8},{-2,30}]

seq=LinearRecurrence[{1,0,0,0,0,1,-1},{1,2,2,4,4,4,5,6},{0,80}]

gf=FindGeneratingFunction[seq,x]

InputForm[%]

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

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

FullSimplify[%,n∈Integers&&n≥0]

Table[(3+(((-1))^n)+4 n-Cos[((n π)/3)]-3 Cos[((2 n π)/3)]-(Sqrt[3]) Sin[((n π)/3)]+((Sin[((2 n π)/3)])/(Sqrt[3])))/6,{n,0,20}]

FullSimplify[(3+(((-1))^n)+4 n-Cos[((n π)/3)]-3 Cos[((2 n π)/3)]-(Sqrt[3]) Sin[((n π)/3)]+((Sin[((2 n π)/3)])/(Sqrt[3])))/6,Mod[n,3]==#]&/@{0,1,2}

Queen n×n

A303003

GraphicsGrid[Partition[Table[HighlightGraph[GraphData[{"Queen",{n,n}},"Graph","Grid"][[1]],GraphData[{"Queen",{n,n}},"TotalDominatingSets"]/.{l_List:>l[[1]],Missing[_,l_]:>l},LabelStyle->Directive[Black,FontFamily->"Times"],PlotLabel->Row[{Style["n",Italic]," == ",n}],VertexSize->{"Scaled",.02}],{n,2,10}],UpTo[4]],ImageSize->1000,PlotLabel->"minimum total dominating configurations for n×n queen graphs"]

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

FindSequenceFunction[Rest@seq,n-1]//Head//Timing

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

Table[2+DifferenceRoot[Function[{\[FormalY],\[FormalN]},{-2-\[FormalY][\[FormalN]]+\[FormalY][3+\[FormalN]]==0,\[FormalY][1]==0,\[FormalY][2]==0,\[FormalY][3]==0,\[FormalY][4]==1}]][-1+n],{n,18}]

bug(350553): FindSequenceFunction[{2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10}, n] results disagrees with sequence

Built-in (COIN)

Do[Print[{{"Queen",{n,n}},{Length[set=TotalDominatingSet[QueenGraph[n,n]]],set}//Timing}],{n,11}]

Gurobi

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

Recognize

seq={0,2,2,2,3,4,4,5,5,6,7,7,8,9,9,10,10,10,11,12};

FindSequenceFunction[Most@seq,n]

InputForm[%]

FindSequenceFunction[seq,n]

bug(350553): FindSequenceFunction[{2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10}, n] results disagrees with sequence

Table[[n-1],{n,20}]

[n]//InputForm

Solve[-3 - \[FormalY][\[FormalN]] + \[FormalY][4 + \[FormalN]] - \[FormalY][7 + \[FormalN]] + \[FormalY][8 + \[FormalN]] == 0/.\[FormalN]->n-8,\[FormalY][n]][[1,1]]

Clear[y]

y[1]=0;
y[2]=y[3]=y[4]=2;
y[5]=3;
y[6]=y[7]=4;
y[8]=5;
y[n_]:=y[n]=y[n-1]-y[n-4]+y[n-8]+3

Array[y,20]

Array[y,19]-seq

RSolve[{y[n-1]-y[n-4]+y[n-8]+3==y[n],y[1]==0,y[2]==y[3]==y[4]==2,y[5]==3,y[6]==y[7]==4},y[n],n]

FunctionExpand[%]

FindGeneratingFunction[seq,x,ValidationLength->2]//Head//Timing

Do[Print[{k,FindLinearRecurrence[Drop[seq,

Rook n×n

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

FindSequenceFunction[Rest@seq,n-1]

Do[Print[{{"Rook",{n,n}},{Length[set=Flatten@FindTotalDominatingSet[RookGraph[n,n],Method->"MOSEK"]],set}//Timing}],{n,14}]

RookComplement n×n

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

SierpinskiCarpet

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

Do[Print[{{"SierpinskiCarpet",n},{Length[set=FindTotalDominatingSet[SierpinskiCarpetGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,8}]

Next term hard to compute (?)

FindSequenceFunction[DeleteMissing@seq,n]

SierpinskiSieve

Matches A032097 for first 5 terms

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

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

Next term is hard to compute (?)

seq=Join[{2},Table[(Fibonacci[2n+1]-Fibonacci[n+2])/2+1,{n,2,20}]]

FindLinearRecurrence[Rest@seq]

Join[{2},LinearRecurrence[{5,-7,1,3,-1},{2,5,14,39,107},20]]

FindSequenceFunction[DeleteMissing@seq,n]

SierpinskiTetrahedron

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

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

Next term is difficult to compute (?)

FindSequenceFunction[DeleteMissing@seq,n]

StackedBook n×n

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

Star

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

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

Sun

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

Sunlet

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

FindSequenceFunction[seq,n-2]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"TotalDominationNumber"],{n,6,10}]

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

seq={4,5,6,8,9,11,12,15,18,21,24};

Table[3(n-9),{n,6,17}]

FindSequenceFunction[seq,n-5]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x,ValidationLength->2]

TorusGrid n×n

A302406

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

seq={3,4,8,10,14,16,23,26,33,36,46,50,60,64};

FindLinearRecurrence[seq]//Head//Timing

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

seq=Table[(3-(((-1))^n) (n-1)+n+2 (n^2)-4 Cos[((n π)/2)]+2 Sin[((n π)/2)])/8,{n,0,70}]

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,-1,1,-1,-1,1},{1,2,3,4,8,10,14},{0,20}]

gf=FindGeneratingFunction[seq,x]

InputForm[gf]

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

Transposition

A303150

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

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

Do[Print[{{"Transposition",n},{Length[set=TotalDominatingSet[TranspositionGraph[n]]],set}//Timing}],{n,7}]

NMinimize

bug(350706): NMinimize[6-transposition total dominating set ILP, var] gives apparently incorrect result

TotalDominatingSetQ[TranspositionGraph[6],{4,8,38,72,78,82,100,127,130,136,156,161,165,175,200,241,243,275,282,290,293,334,341,356,375,378,381,404,433,449,463,470,474,498,501,507,541,562,597,607,608,625,648,654,659,693,715}]

Range@VertexCount[TranspositionGraph[6]]===VertexList[TranspositionGraph[6]]

GUROBI

bug(350706):

iliang: GUROBI can in fact get a result (given ~6 days and ~100 GB of RAM)

Explored 694911855 nodes (52486844350 simplex iterations) in 470643.80 seconds
Thread count was 32 (of 32 available processors)
Solution count 10: 64 65 66 ... 95
Optimal solution found (tolerance 1.00e-04)
Best objective 6.400000000000e+01, best bound 6.400000000000e+01, gap 0.0000%

Out[1]= {470645., {64, {1, 2, 34, 48, 63, 65, 77, 91, 97, 110, 131, 136, 157, 158, 173, 190, 196, 207, 227, 240, 247, 261, 278, 281, 297, 298, 316, 318, 343, 352, 372, 375, 381, 383, 389, 406, 409, 410, 444, 451, 453, 470, 473, 487, 500, 502, 517, 519, 533, 546, 566, 573, 579, 588, 602, 605, 630, 636, 657, 671, 673, 686, 712, 715}}}

EdgeList[TranspositionGraph[6]]===GraphData[{"Transposition", 6},"EdgeList"]

TotalDominatingSetQ[TranspositionGraph[6],set={1,2,34,48,63,65,77,91,97,110,131,136,157,158,173,190,196,207,227,240,247,261,278,281,297,298,316,318,343,352,372,375,381,383,389,406,409,410,444,451,453,470,473,487,500,502,517,519,533,546,566,573,579,588,602,605,630,636,657,671,673,686,712,715}]

Triangular

A004523

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

Do[Print[{{"Triangular",n},{Length[set=TotalDominatingSet[TriangularGraph[n]]],set}//Timing}],{n,2,15}]

seq={2,2,3,4,4,5,6,6,7,8,8,9};

FindLinearRecurrence[seq]

LinearRecurrence[{1,0,1,-1},{0,1,2,2},{0,20}]

seq=Table[Floor[2n/3],{n,0,75}]

FullSimplify[FindSequenceFunction[Rest@Take[seq,30],n],n∈Integers&&n>0]

Table[(6 n+3 Cos[((2 n π)/3)]-(Sqrt[3]) Sin[((2 n π)/3)]-3)/9,{n,0,20}]

Floor[2Range[0,20]/3]

FindGeneratingFunction[seq,x]

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

TriangularGrid

A302486

seq=Table[GraphData[{"TriangularGrid",n},"TotalDominationNumber"],{n,0,20}]

seq=BFileSequence[302486]

FindLinearRecurrence[Drop[seq,2]]//Head//Timing

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

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

COIN

Do[Print[{{"TriangularGrid",n},{Length[set=FindTotalDominatingSet[TriangularGridGraph[n]]//Flatten],set}//Timing}],{n,20}]

Gurobi

Do[Print[{{"TriangularGrid",n},{Length[set=FindTotalDominatingSet[TriangularGridGraph[n],Method->"Gurobi"]//Flatten],set}//Timing}],{n,20}]

seq={2,2,4,5,6,8,10,12,15,17,20,23,26,30,33,36,40,45,49,54,58,63,69,74};

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

TriangularHoneycombAcuteKnight

A342373

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

seq={6,6,6,6,10,12,15,18,18,21,26,30,33,36,36,42,47,54,57,60,63,69};

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

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

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

Do[Print[{n,Flatten[FindTotalDominatingSet[TriangularHoneycombAcuteKnightGraph[n]]]//Length//Timing}],{n,3,20}]

COIN

Do[Print[{{"TriangularHoneycombAcuteKnight",n},{Length[set=FindTotalDominatingSet[TriangularHoneycombAcuteKnightGraph[n]]//Flatten],set}//Timing}],{n,3,30}]

Gurobi

TriangularHoneycombBishop

A004523

Inferred for n > 18:

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"TotalDominationNumber"],{n,20}]

Table[Floor[2(n+1)/3],{n,2,18}]==Take[seq,{2,18}]

Do[Print[{gn=GraphData[{"TriangularHoneycombBishop",n},"#"],Flatten@FindTotalDominatingSet[GraphData[gn],Method->"MOSEK"]//Timing}],{n,20}]

20 needs 59+ GB

TriangularHoneycombObtuseKnight

A342374

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

COIN

Do[Print[{{"TriangularHoneycombObtuseKnight",n},{Length[set=FindTotalDominatingSet[TriangularHoneycombObtuseKnightGraph[n]]//Flatten],set}//Timing}],{n,5,30}]

Gurobi

Do[Print[{{"TriangularHoneycombObtuseKnight",n},{Length[set=FindTotalDominatingSet[TriangularHoneycombObtuseKnightGraph[n,Method->"Gurobi"]]//Flatten],set}//Timing}],{n,5,30}]

seq={8,7,7,8,9,12,15,17,19,20,21,24,25,28,31,34,37,39,42};

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

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

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

TriangularHoneycombQueen

A004526(n) for n > 2

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

Do[Print[{{"TriangularHoneycombQueen",n},{Length[set=FindTotalDominatingSet[TriangularHoneycombQueenGraph[n]]//Flatten],set}//Timing}],{n,20}]

seq={1,2,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10};

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

gf=x FindGeneratingFunction[seq,x]

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

TriangularHoneycombRook

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

TriangularSnake

Table[GraphData[{"TriangularSnake",2n-1},"TotalDominationNumber"],{n,10}]

Table[Length@Flatten@FindTotalDominatingSet[TriangularSnakeGraph[2n-1],Method->"Gurobi"],{n,30}]

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

Web

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

FindSequenceFunction[seq,n-2]

Wheel

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

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

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"TotalDominationNumber"],{n,2,20}]

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

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

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

gf=FindGeneratingFunction[seq,x]

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

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