Connected Domination Number

Author

Eric W. Weisstein
March 27, 2025

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

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

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

Counts

FullTally[l_List]:=Module[{t=Sort[Tally[l]],f,r},
If[(f=t[[All,1]])===(r=Range@@f[[{1,-1}]]),t,Sort[Join[t,{#,0}&/@Complement[r,f]]]]
]

FullTally[Sort[#]]&/@(values=Table[ConnectedDominationNumber/@ConnectedGraphs[n],{n,7}])//Column

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/ConnectedDominationNumber"];
FullTally[Sort[#]]&/@(values=Get/@FileNames["*.m"])//Column

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

A286958

Flatten[tallies]

A001349

Total/@tallies

Length/@tallies

Not in OEIS:

Total/@values

Count table

Remember to update MaximumLeafNumber as well

GraphDataCountTable["ConnectedDominationNumber",{"Alkane"->000027,"Andrasfai"->122553,"Antiprism"->000027,"Apollonian"->291773,"Barbell"->007395,"BlackBishop"->00027,"Book"->007395,"Centipede"->000027,"CocktailParty"->007395,"Complete"->000012,"CompleteBipartite"->040000,"CompleteTripartite"->040000,"CrossedPrism"->005843,"Crown"->010709,"Cycle"->000027,"CycleComplement"->007395,"Dipyramid"->040000,"DorogovtsevGoltsevMendes"->115098,"DoubleCone"->000012,"FibonacciCube"->291298,"Flower"->42948,"Gear"->004526,"Goldberg"->004767,{"Grid",2}->369692,"Helm"->000027,"Keller"->010709,"King"->370428,"Knight"->382047,"Ladder"->27,"LucasCube"->382046,"MoebiusLadder"->000027,"Mycielski"->27,"Pan"->000027,"Path"->000027,"PathComplement"->007395,"PlummerToft"->7395,"Prism"->000027,"Queen"->381091,"Rook"->000027,"RookComplement"->122553,"StackedBook"->000027,"Star"->000012,"Sun"->004526,"Sunlet"->000027,"Trapezohedron"->010709,"Triangular"->028310,"TriangularGrid"->379353,"TriangularHoneycombBishop"->27,"TriangularHoneycombObtuseKnight"->382090,"TriangularHoneycombQueen"->004526,"TriangularSnake"->000027,"Web"->000027,"Wheel"->000012,"WhiteBishop"->27,"Zebra"->382071}]

Code

<<MathWorld`Graphs`

transformations[n_,points_]:=Module[{rot90,rot180,rot270,reflH,reflV,reflD1,reflD2},
  rot90={n+1-#2,#} & @@@ points;
  rot180={n+1-#,n+1-#2} & @@@ points;
  rot270={#2,n+1-#} & @@@ points; 
  reflH={#,n+1-#2} & @@@ points;
  reflV={n+1-#,#2} & @@@ points;
  reflD1=Reverse /@ points;
  reflD2={n+1-#2,n+1-#} & @@@ points;
  Union[{points,rot90,rot180,rot270,reflH,reflV,reflD1,reflD2}]
]

SymmetricallyExpandedConfigurations[g_Graph,sets_]:=Module[{emb=GraphEmbedding[g],n=Sqrt[VertexCount[g]],rules},
rules=Thread[emb->Range[n^2]];
Sort[Sort/@Union[Flatten[Union[Sort/@(transformations[n,emb[[#]]])]&/@sets,1]]/.rules]
]

canonicalorientation[n_,points_]:=Union[Sort/@transformations[n,points]][[1]]

DistinctArrangements[g_Graph,sets_]:=Module[{n=Sqrt[VertexCount[g]],emb=GraphEmbedding[g]},
If[Min[Flatten[emb]]==0,emb+=1];
Union[canonicalorientation[n,emb[[#]]]&/@sets]
]

DistinctArrangementsWithTallies[g_Graph,{}]:={}
DistinctArrangementsWithTallies[g_Graph,sets_]:=Module[{n=Sqrt[VertexCount[g]],emb=GraphEmbedding[g],mins},
mins=Min/@Transpose[emb];
emb=#+1-mins&/@emb;
Counts[canonicalorientation[n,emb[[#]]]&/@sets]
]

VerticalDividers[lens_,n_]:=Append[Flatten[Join[{Thick},Table[True,#-1]]&/@Ceiling[lens/n]],Thick]

SymmetricallyDistinctTallyGraphic[class_String,nmax_Integer,rows_:10]:=SymmetricallyDistinctTallyGraphic[class,Range[nmax],rows]

MostSymmetricConfiguration[class_,prop_,n_,opts___?OptionQ]:=Module[
{
res,
configs=GraphData[{class,{n,n}},prop],
diag=Lookup[{opts},"Diagonal",False],
nice
},
If[MissingQ[configs],
res=Quiet@Import[
FileNameJoin[{$GraphDataDirectory,"Properties",prop,GraphNameToFileName[{class,{n,n}}]<>".gz"}]]
];
If[ListQ[res],configs=res,configs=Replace[configs,Missing[_,l_List]:>{l}]];
nice=SortBy[Normal@DistinctArrangementsWithTallies[
GraphData[{class,{n,n}},"Graph","Grid"][[1]],
configs
],Last];
If[diag,SelectFirst[nice[[All,1]],DiagonalArrangementQ[#,n]&],nice[[1,1]]]
]

DiagonalArrangementQ[config_,n_]:=AllTrue[config,#[[1]]==#[[2]]&]

ArrangementGraphic[class_String,prop_,nrange_List,rows_:10,opts___?OptionQ]:=Module[
{
table,res,
label=If[Length[nrange]==1,First@nrange,Style["n",Italic]],
mesh=Lookup[{opts},Mesh,Automatic]
},
table=Table[
ArrayPlot[
SparseArray[Evaluate@Thread[Reverse/@MostSymmetricConfiguration[class,prop,n,opts]->1],{n,n}],Mesh->Replace[mesh,Automatic->(n<11)],DataRange->{{0,n},{0,n}}
],
{n,nrange}];
Labeled[
GraphicsGrid[
Partition[table,UpTo[rows]],
ImageSize->1000
],
Style[Row[{label," × ",label," "<>class}],Directive[18,Bold,FontFamily->"Times"]],
Top
]
]

Parametrized families

<<MathWorld`Graphs`

Andrasfai

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

Antelope n×n

Inferred for for n > 10:

Table[GraphData[{"Antelope",{n,n}},"ConnectedDominationNumber"],{n,20}]/.Missing["NotApplicable"]->"-"

Antiprism

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

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

Apollonian

A291773

=== DominationNumber

seq=Table[GraphData[{"Apollonian",n},"ConnectedDominationNumber"],{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},"ConnectedDominationNumber"],{n,3,20}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"ConnectedDominationNumber"],{n,10}]

BlackBishop n×n

Inferred for for n > 10:

Table[GraphData[{"BlackBishop",{n,n}},"ConnectedDominationNumber"],{n,20}]

Grid[DeleteCases[Table[
{
n,
set=Replace[GraphData[gn={"BlackBishop",{n,n}},"MinimumConnectedDominatingSets"],{l_List:>First[l],Missing[_,l_]:>l}],
HighlightGraph[GraphData[gn,"Graph"],set,VertexSize->Medium]
},{n,20}],{_,_Missing,_}],Dividers->All]

Table[GraphData[{"BlackBishop",{n,n}},"Graph","Labeled"],{n,11,13,2}]

Table[GraphData[{"BlackBishop",{n,n}},"Graph","Labeled"],{n,12,14,2}]

(rules=Table[Rule[{"BlackBishop",{n,n}},
If[Mod[n,2]==1,
Range[(n+3)/2,Binomial[n,2],(n+1)/2],
Union@@{Range[n/2+1,n^2/2-n,n+1],Range[n+2,n^2/2,n+1]}
]],
{n,11,20}])//Column

HighlightGraph[GraphData[#],#2,VertexSize->Large]&@@@rules

Book

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

Caveman

GraphData[{"Caveman",{3,4}},"Graph","Labeled"]

GraphData[{"Caveman",{3,4}},"MinimumConnectedDominatingSets"]

data={#,n=GraphData[#,"NotationRules","Caveman"],GraphData[#,"ConnectedDominationNumber"],2n[[1]]-1}&/@GraphData["Caveman"]

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

DeleteCases[Block[{m,n},{#,GraphData[#,"ConnectedDominationNumber"],{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"];Piecewise[{{1, Min[m, n] == 1}}, 2]}]&/@GraphData["CompleteBipartite"],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

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

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

DorogovtsevGoltsevMendes

A115098

=== DominationNumber

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

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

Empty

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

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

FibonacciCube

A291298

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

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

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

Do[
Print[
{
gn={"FibonacciCube",n},
{
set=MemoryConstrained[FindConnectedDominatingSet[GraphData[gn],Debug->False],50*^9];
If[ListQ[set],Length[set=Flatten[set]],$Failed],
set
}//Timing}],{n,9}]

Fiveleaper n×n

(seq=Table[GraphData[{"Fiveleaper",{n,n}},"ConnectedDominationNumber"],{n,20}])/.Missing["NotApplicable"]->"-"

Do[
Print[
{
gn={"Fiveleaper",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->n>9];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,8,15}]

Flower

A042948

Inferred for n > 13:

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

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

FoldedCube

Table[GraphData[{"FoldedCube",n},"ConnectedDominationNumber"],{n,2,10}]

Gear

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

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

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

%==seq

Giraffe n×n

(seq=Table[GraphData[{"Giraffe",{n,n}},"ConnectedDominationNumber"],{n,20}])/.Missing["NotApplicable"]->"-"

Do[
Print[
{
gn={"Giraffe",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->n>9];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,8,15}]

TextGrid[Table[{n,Replace[GraphData[{"Giraffe",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]},{n,20}],Dividers->All]

Goldberg

A004767

Inferred for n > 8:

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

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

TextGrid[Table[{n,Replace[GraphData[{"Goldberg",n},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]},{n,3,20}],Dividers->All]

Grid m×n

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

DeleteCases[Table[GraphData[{"Grid",{m,n}},"ConnectedDominationNumber"],{n,10},{m,n}],_Missing,{2}]//Column

Grid n×n

A369692

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

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

a(3*n) <= n*(3*n+1); a(3*n-1) <= 3*n^2 - 1; a(3*n-2) <= (n-1)*(3*n+1). Conjecturally these inequalities hold with equality for n > 1. - Andrew Howroyd, Mar 06 2024

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

Do[
Print[
{
gn={"Grid",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->(n>8)];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,16}]

Using known connected domination number:

Do[
Print[
{
gn={"Grid",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},Debug->(n>8)];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,9,16}]

TextGrid[Table[{n,Replace[GraphData[{"Grid",{n,n}},"MinimumConnectedDominatingSets"],l_List:>l[[1]]]},{n,20}],Dividers->All]

Grid k×m×n

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

DeleteCases[Table[GraphData[{"Grid",{n,n,n}},"ConnectedDominationNumber"],{n,10},{m,n},{k,m}],_Missing,∞]//Column

Grid n×n×n

Possibly (n^2)

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

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

HalvedCube

Table[GraphData[{"HalvedCube",n},"ConnectedDominationNumber"],{n,2,10}]

Hanoi

Possibly  (4^(n-1))

Table[GraphData[{"Hanoi",n},"ConnectedDominationNumber"],{n,6}]

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

Table[GraphData[{"Hanoi",n},"MinimumConnectedDominatingSetCount"],{n,6}]

HighlightGraph[GraphData[{"Hanoi",2}],#,VertexSize->Medium]&/@GraphData[{"Hanoi",2},"MinimumConnectedDominatingSets"]

HighlightGraph[GraphData[{"Hanoi",3}],#,VertexSize->Medium]&/@GraphData[{"Hanoi",3},"MinimumConnectedDominatingSets"]

Helm

Table[GraphData[{"Helm",n},"ConnectedDominationNumber"],{n,3,20}]

Hypercube

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

Agrees with A000123 (next term 14) and A002088 (next term 12)

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

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

<<MathWorld`Graphs`

Do[Print[{
gn={"Hypercube",n},
{
set=MemoryConstrained[FindConnectedDominatingSet[GraphData[gn],{GraphData[{"Hypercube",n},"DominationNumber"],2^n},Method->"LinearOptimization"],20*^9];
If[ListQ[set],Length[set=Flatten[set]],$Failed],
set}//Timing}],{n,0,7}]

Keller

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

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

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

King n×n

A370428

Table[GraphData[{"King",{n,n}},"ConnectedDominationNumber"],{n,20}]

Do[
Print[
{
gn={"King",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->(n>10)];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,16}]

TextGrid[Table[{n,Replace[GraphData[{"King",{n,n}},"MinimumConnectedDominatingSets"],l_List:>l[[1]]]},{n,20}],Dividers->All]

Knight m×n

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

seq=Table[GraphData[{"Knight",{m,n}},"ConnectedDominationNumber"],{n,10},{m,n}]

Knight n×n

A382047

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

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

Compute

Do[
Print[
{
gn={"Knight",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn]];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,4,10}]

One known

TextGrid[Table[{n,Replace[GraphData[{"Knight",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]},{n,20}],Dividers->All]

Ladder

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

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

LadderRung

Table[GraphData[{"LadderRung",n},"ConnectedDominationNumber"],{n,5}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"ConnectedDominationNumber"],{n,11}]

LucasCube

A382046

Table[GraphData[{"LucasCube",n},"ConnectedDominationNumber"],{n,15}]

Do[
Print[
{
gn={"LucasCube",n},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->False];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,10}]

...ran overnight...

MengerSponge

Table[GraphData[{"MengerSponge",n},"ConnectedDominationNumber"],{n,3}]

MoebiusLadder

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

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

Mycielski

Inferred for n > 7:

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

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

Do[
Print[
{
gn={"Mycielski",n},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->(n>5)];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,11}]

Do[
Print[
{
gn={"Mycielski",n},
{
set=FindConnectedDominatingSet[GraphData[gn],{n},Debug->n>6];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,11}]

Odd

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

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

Pan

Table[GraphData[{"Pan",n},"ConnectedDominationNumber"],{n,3,20}]

Path

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

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

Pell

Table[GraphData[{"Pell",n},"ConnectedDominationNumber"],{n,9}]

Do[
Print[
{
gn={"Pell",n},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->False];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,6}]

TextGrid[Table[{n,Replace[GraphData[{"Pell",n},"MinimumConnectedDominatingSets"],l_List:>l[[1]]]},{n,9}],Dividers->All]

Prism

A000027

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

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

Queen m×n

DeleteCases[Block[{m,n},{#,GraphData[#,"ConnectedDominationNumber"],{m,n}="Queen"/.GraphData[#,"NotationRules"];Piecewise[{{Min[m,n],Min[m,n]<3}},Floor[Max[m,n]/2]]}]&/@GraphData["Queen"],{_,x_,x_}]

Queen n×n

A381091

Table[GraphData[{"Queen",{n,n}},"ConnectedDominationNumber"],{n,20}]

Compute

Do[Print[{n,set=MemoryConstrained[Flatten@FindConnectedDominatingSet[QueenGraph[n,n],Method->"SelectFirst"],100*^9],If[ListQ[set],Length[set],$Failed]}//Timing],{n,11}]

Do[Print[{
{"Queen",{n,n}},
{
set=MemoryConstrained[Flatten@FindConnectedDominatingSet[QueenGraph[n,n],Method->{"LinearOptimization",Automatic}],20*^9];
If[ListQ[set],Length[set],$Failed],
set}//Timing}],{n,11}]

Do[Print[{
{"Queen",{n,n}},
{
set=MemoryConstrained[Flatten@FindConnectedDominatingSet[QueenGraph[n,n],Method->"LinearOptimization"],20*^9];
If[ListQ[set],Length[set],$Failed],
set}//Timing}],{n,11}]

Figure

ArrangementGraphic["Queen","MinimumConnectedDominatingSets",Range[13],5,Mesh->True]

Diagonal figure

ArrangementGraphic["Queen","MinimumConnectedDominatingSets",Range[11],6,"Diagonal"->True,Mesh->True]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"ConnectedDominationNumber"],{n,10}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"ConnectedDominationNumber"],{n,20}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"ConnectedDominationNumber"],{n,4}]

Table[HighlightGraph[GraphData[{"SierpinskiCarpet",n},"Graph"],GraphData[{"SierpinskiCarpet",n},"MinimumConnectedDominatingSets"]/.{{l_List,___}:>l,Missing[_,l_List]:>l},VertexSize->{"Scaled",.02}],{n,1}]

SierpinskiGasket

Table[GraphData[{"SierpinskiGasket",n},"ConnectedDominationNumber"],{n,7}]

Subtract@@@Select[Table[GraphData[{"SierpinskiGasket",n},{"ConnectedDominationNumber","DominationNumber"}],{n,7}],FreeQ[Missing]]

Do[
Print[
{
gn={"SierpinskiGasket",n},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->False];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,4}]

Table[HighlightGraph[GraphData[{"SierpinskiGasket",n},"Graph"],GraphData[{"SierpinskiGasket",n},"MinimumConnectedDominatingSets"]/.{{l_List,___}:>l,Missing[_,l_List]:>l},VertexSize->{"Scaled",.02}],{n,4}]

SierpinskiTetrahedron

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

Star

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

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

Sun

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

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

%==seq

Sunlet

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

Tetrahedral

Possibly 2 (n - 4)

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

TorusGrid n×n

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

A061925

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

Do[
Print[
{
gn={"TorusGrid",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->(n>5)];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,3,7}]

Transposition

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

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

Trapezohedron

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

Triangular

seq=Table[GraphData[{"Triangular",n},"ConnectedDominationNumber"],{n,3,10}]

TriangularGrid

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

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

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

Subtract@@@Select[Table[GraphData[{"TriangularGrid",n},{"ConnectedDominationNumber","DominationNumber"}],{n,20}],FreeQ[Missing]]

Table[GraphData[{"TriangularGrid",n},"MinimumConnectedDominatingSets"]/.{{l_List,___}:>l,Missing[_,l_List]:>l},{n,6}]//Column

Table[HighlightGraph[GraphData[{"TriangularGrid",n},"Graph","Labeled"],GraphData[{"TriangularGrid",n},"MinimumConnectedDominatingSets"]/.{{l_List,___}:>l,Missing[_,l_List]:>l},VertexSize->Medium],{n,3,6}]

TriangularHoneycombAcuteKnight

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

Multicolumn[Table[GraphData[{"TriangularHoneycombAcuteKnight",n}],{n,5}]]

TriangularHoneycombBishop

Inferred for n > 9:

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

Grid[DeleteCases[Table[
{
n,
set=Replace[GraphData[{"TriangularHoneycombBishop",n},"MinimumConnectedDominatingSets"],{l_List:>First[l],Missing[_,l_]:>l}],
HighlightGraph[GraphData[{"TriangularHoneycombBishop",n},"Graph","TriangularGrid"][[1]],set]
},{n,20}],{_,_Missing,_}],Dividers->All]

Table[GraphData[{"TriangularHoneycombBishop",n},"Graph",{"TriangularGrid","Labeled"}],{n,9,11}]

rules=Table[Rule[gn=GraphData[{"TriangularHoneycombBishop",n},"#"],
Sort[SortBy[(SortBy[#,Function[f,N[f[[2,1]]]]]&/@SplitBy[SortBy[
MapIndexed[{#2[[1]],#}&,GraphData[gn,"Embeddings","TriangularGrid"][[1]]],
#[[2,2]]&],#[[2,2]]&])[[All,1,All]],N[#[[2,2]]]&][[2;;,1]]]
],{n,13,20}]

TriangularHoneycombObtuseKnight

A382090

(seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ConnectedDominationNumber"],{n,20}])/.Missing["NotApplicable"]->"-"

TextGrid[Table[{n,Replace[GraphData[{"TriangularHoneycombObtuseKnight",n},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]},{n,20}],Dividers->All]

Do[
Print[
{
gn={"TriangularHoneycombObtuseKnight",n},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->n>10];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,6,20}]

TriangularHoneycombQueen

Inferred for n > 10:

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

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

Grid[DeleteCases[Table[
{
n,
set=Replace[GraphData[{"TriangularHoneycombQueen",n},"MinimumConnectedDominatingSets"],{l_List:>First[l],Missing[_,l_]:>l}],
HighlightGraph[GraphData[{"TriangularHoneycombQueen",n},"Graph","TriangularGrid"][[1]],set]
},{n,20}],{_,_Missing,_}],Dividers->All]

Table[GraphData[{"TriangularHoneycombQueen",n},"Graph",{"TriangularGrid","Labeled"}][[1]],{n,9,12}]

With[{n=11},{Binomial[Ceiling[n/2],2]+1,Binomial[Ceiling[n/2]+1,2]}]

n=.

(rules=Table[{"TriangularHoneycombQueen",n}->Range@@{Binomial[Ceiling[n/2],2]+1,Binomial[Ceiling[n/2]+1,2]},{n,11,20}])//Column

TriangularHoneycombRook

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

Web

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

Wheel

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

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

WhiteBishop n×n

Inferred for n > 10:

Table[GraphData[{"WhiteBishop",{n,n}},"ConnectedDominationNumber"],{n,2,20}]

Grid[DeleteCases[Table[
{
n,
set=Replace[GraphData[gn={"WhiteBishop",{n,n}},"MinimumConnectedDominatingSets"],{l_List:>First[l],Missing[_,l_]:>l}],
HighlightGraph[GraphData[gn,"Graph","WhitePiece"][[1]],set,VertexSize->Medium]
},{n,3,20,2}],{_,_Missing,_}],Dividers->All,Alignment->Left]

HighlightGraph[GraphData[{"WhiteBishop",{7,7}}],#,VertexSize->Medium]&/@GraphData[{"WhiteBishop",{7,7}},"MinimumConnectedDominatingSets"]

Table[GraphData[{"WhiteBishop",{n,n}},"Graph","Labeled"],{n,11,13,2}]

(rules=Table[Rule[{"WhiteBishop",{n,n}},
Union@@{Range[(n+3)/2,(n^2-1)/2-n,(n+1)/2],{n+1}}
],
{n,11,20,2}])//Column

HighlightGraph[GraphData[#],#2,VertexSize->Large]&@@@rules

Zebra n×n

A382071

(seq=Table[GraphData[{"Zebra",{n,n}},"ConnectedDominationNumber"],{n,20}])/.Missing["NotApplicable"]->"-"

Do[
Print[
{
gn={"Zebra",{n,n}},
{
set=FindConnectedDominatingSet[GraphData[gn],Debug->True];
If[ListQ[set],Length[set=Flatten@set],$Failed],
set
}//Timing}],{n,6,12}]

TextGrid[Table[{n,Replace[GraphData[{"Zebra",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]},{n,20}],Dividers->All]

Grid[DeleteCases[Table[
{
n,
set=Replace[GraphData[gn={"Zebra",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>First[l],Missing[_,l_]:>l}],
HighlightGraph[GraphData[gn,"Graph","Grid"][[1]],set,VertexSize->If[n==1,.01,{"Scaled",.03}]]
},{n,20}],{_,_Missing,_}],Dividers->All,Alignment->Left]

Algorithms

LinearOptimization

DeleteCases[Monitor[{g=#,GraphData[#,"ConnectedDominationNumber"],ConnectedDominationNumber[GraphData[#],Method->"LinearOptimization"]}&/@GraphData["Connected",;;11],g],{_,x_,x_}]//Timing

Loop

DeleteCases[Monitor[{g=#,GraphData[#,"ConnectedDominationNumber"],ConnectedDominationNumber[GraphData[#],Method->"Loop"]}&/@GraphData["Connected",;;11],g],{_,x_,x_}]//Timing

NextSubset

DeleteCases[Monitor[{g=#,GraphData[#,"ConnectedDominationNumber"],ConnectedDominationNumber[GraphData[#],Method->"NextSubset"]}&/@GraphData["Connected",;;11],g],{_,x_,x_}]//Timing

SelectFirst

DeleteCases[Monitor[{g=#,GraphData[#,"ConnectedDominationNumber"],ConnectedDominationNumber[GraphData[#],Method->"SelectFirst"]}&/@GraphData["Connected",;;11],g],{_,x_,x_}]//Timing