Minimum Connected Dominating Set

Author

Eric W. Weisstein
April 7, 2025

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

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

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

Count table

GraphDataCountTable["MinimumConnectedDominatingSetCount",
Join[
{"Andrasfai"->016789,"Antiprism"->046092,"BlackBishop"->381726,"CocktailParty"->046092,"CompleteBipartite"->000290,"CompleteTripartite"->033428,"Crown"->033487,"CycleComplement"->055998,"DiagonalIntersection"->382855,"Dipyramid"->005843,"FibonacciCube"->382273,"Flower"->382500,"FoldedCube"->382299,"Gear"->141310,"Goldberg"->382384,{"Grid",2}->381730,"HalvedCube"->382205,"Hypercube"->382275,"Keller"->381761,"King"->382206,"Knight"->382207,"LadderRung"->000038,"LucasCube"->381729,"MoebiusLadder"->005843,"Mycielski"->381728,"Odd"->382276,"Path"->294619,"PathComplement"->000217,"Pell"->381755,"Prism"->005893,"Queen"->373394,"Rook"->103517,"RookComplement"->179058,"TorusGrid"->382530,"Trapezohedron"->005843,"Triangular"->373395,"TriangularGrid"->373393,"TriangularHoneycombBishop"->132609,"TriangularHoneycombObtuseKnight"->380859,"TriangularHoneycombQueen"->381722,"WhiteBishop"->381727},
Thread[{"Bishop","Camel","Empty","TriangularHoneycombRook"}->7],
Thread[{"Complete","Cycle","Pan"}->000027], (* 1, 2, 3, ... *)
Thread[{"Centipede","Spoke"}->054977],Thread[{"Alkane","Barbell","Book","DoubleCone","Helm","Star","Sunlet","TriangularSnake","Web","Wheel"}->000012]]]

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]

SymmetricallyDistinctTallyGraphic[class_String,nrange_List,rows_:10]:=Module[
{
table,res,
label=If[Length[nrange]==1,First@nrange,Style["n",Italic]]
},
table=Table[
ArrayPlot[
SparseArray[Evaluate@Thread[Reverse/@#->1],{n,n}],Mesh->(n<13),DataRange->{{0,n},{0,n}},
PlotLabel->#2
]&@@@SortBy[Normal[DistinctArrangementsWithTallies[
GraphData[{class,{n,n}},"Graph","Grid"][[1]],
If[MissingQ[res=GraphData[{class,{n,n}},"MinimumConnectedDominatingSets"]],Import[FileNameJoin[{$GraphDataDirectory,"Properties","MinimumConnectedDominatingSets",GraphNameToFileName[{class,{n,n}}]<>".gz"}]],
res]]],
Last
],
{n,nrange}];
Labeled[
GraphicsGrid[
Flatten[Partition[#,UpTo[rows]]&/@table,1],
Dividers->{Thick,VerticalDividers[Length/@table,rows]},
ImageSize->1000
],
Style[Row[{label," × ",label," "<>class}],Directive[18,Bold,FontFamily->"Times"]],
Top
]
]

Parametrized families

Andrasfai

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

FindSequenceFunction[DeleteMissing@seq,n]

Antiprism

A046092

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

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

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

Apollonian

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

Grid[DeleteCases[Table[
{
n,
sets=GraphData[{"Apollonian",n},"MinimumConnectedDominatingSets"]/.Missing[_,l_List]:>{l},
HighlightGraph[GraphData[{"Apollonian",n},"Graph"],#,VertexSize->{"Scaled",(Sqrt[n])/40}]&/@sets
},{n,6}],{_,_Missing,_}],Dividers->All,Alignment->Left]

Barbell

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

Bishop n×n

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

BlackBishop n×n

A381726

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

seq==Join[{1,2},Table[Sum[(((2 k-1))^(n-2k-1)) (((n-2 k))^(2 (k-1))),{k,Floor[(n-1)/2]}],{n,3,20}]]

FindSequenceFunction[Drop[BFileSequence[381726],2],n-2]//Head//Timing

FindGeneratingFunction[BFileSequence[381726],x]//Head//Timing

FullSimplify[n^(k-1)k^(n-1)/.{n->n-2k,k->2k-1}]

Sum[(((-1+2 k))^(-1-2 k+n)) (((-2 k+n))^(2 (-1+k))),{k,Floor[(n-1)/2]}]

Book

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

Centipede

A054977

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

CocktailParty

A046092

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

FindSequenceFunction[seq,n]

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

Complete

A000027

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

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

CompleteBipartite m×n

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

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

CompleteBipartite n×n

A000290

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

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

FindSequenceFunction[Rest@seq,n-1]//Factor

CompleteTripartite k×m×n

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

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

Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumConnectedDominatingSetCount"],(k^2)+(m^2)+(n^2)}&/@GraphData["CompleteTripartite"]]]

CompleteTripartite n×n×n

A033428

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

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

Table[3n^2,{n,10}]

CrossedPrism

Inferred for n > 7:

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

FindLinearRecurrence[Rest@DeleteMissing@seq]

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

gf=(x^2) FindGeneratingFunction[DeleteMissing@seq,x]

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

Table[Piecewise[{{30,n==2}},(2^(n-2))(15n+4)],{n,2,10}]

Crown

A033487

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

FindLinearRecurrence[Rest@DeleteMissing@seq]

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

Table[6Binomial[n+1,4],{n,3,20}]

CubeConnectedCycle

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

Cycle

A000027

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

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

CycleComplement

A055998

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

seq==Table[Piecewise[{{0,n==3||n==4},{5,n==5}},(n-5)n/2],{n,3,20}]

DiagonalIntersection

A382855

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

Dipyramid

A005843

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

gf=(x^3)FindGeneratingFunction[seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n≥3]

DorogovtsevGoltsevMendes

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

Grid[DeleteCases[Table[
{
n,
sets=GraphData[{"DorogovtsevGoltsevMendes",n},"MinimumConnectedDominatingSets"]/.Missing[_,l_List]:>{l},
HighlightGraph[GraphData[{"DorogovtsevGoltsevMendes",n},"Graph"],#,VertexSize->{"Scaled",(Sqrt[n])/40}]&/@sets
},{n,7}],{_,_Missing,_}],Dividers->All,Alignment->Left]

DoubleCone

A000012

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

Empty

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

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

FibonacciCube

A382273

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

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

Do[
Print[{gn=GraphData[{"FibonacciCube",n},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,9}]

Do[
Print[{gn=GraphData[{"FibonacciCube",n},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,{9}}]

Flower

A382500

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

FoldedCube

A382299

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

Gear

A141310

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

LinearRecurrence[{0,1,1},{3,2,5},20]

GeneralizedPetersen

Sort[{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumConnectedDominatingSetCount"]}&/@GraphData["GeneralizedPetersen"]]

Goldberg

A382384

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

Grid 3×n

Entity["Graph",{"Grid",{3,n}}]["MinimumConnectedDominatingSetCount"]

seq=Table[GraphData[{"Grid",Sort[{3,n}]},"MinimumConnectedDominatingSetCount"],{n,10}]

Grid m×n

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

Block[{m,n},Sort[{{m,n}="Grid"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumConnectedDominatingSetCount"],Piecewise[{{2,Min[m,n]==1}},m n+2]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&]]]

Grid n×n

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

A381730

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

Position[seq,16]//Flatten

A369692

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

One set known

TextGrid[Table[
{
n,
GraphData[gn={"Grid",{n,n}},"ConnectedDominationNumber"],
If[ListQ[set=Replace[GraphData[gn,"MinimumConnectedDominatingSets"],{{}->{},Missing[_,l_List]:>l,l_List:>l[[1]]}]],Length@set,"-"],
GraphData[gn,"MinimumConnectedDominatingSetCount"],
set
},{n,20}],Dividers->All,Alignment->{{{Decimal},Left}}]

Configurations for 1-12

image=Import["https://oeis.org/A369692/a369692.pdf"][[1]]

tiles=Flatten[ImagePartition[image,ImageDimensions[image]/{4,3}]]

bug(458348): ImageCrop and RemoveBackground fail to remove white background

img=;

ImageCrop[img]

DominantColors[img,3]

RemoveBackground[img,White]

dim=BorderDimensions[img]

bug(458348): ImageCrop and RemoveBackground fail to remove white background

MyImageCrop[img_]:=Module[{dim=BorderDimensions[img]},ImagePad[img,-dim]]

grids=Table[MyImageCrop[ImageTake[tiles[[n]],{36-If[n>4,3,0],-1}]],{n,Length[tiles]}]

DominantColors[grids[[4]],MinColorDistance->.1]

MyImagePartition[img_,n_]:=Module[{width,height},
{width,height}=ImageDimensions[img];
Table[ImageTake[img,{i,i+1}width/n,{j,j+1}height/n],{i,0,n-1},{j,0,n-1}]
]

GridPositions[img_,n_]:=Module[
{
parts=Map[
ImageCrop[#,ImageDimensions[#]-3]&,
MyImagePartition[img,n],
{2}
],
gray=
},
Position[parts,_?(ColorDistance[DominantColors[#,1][[1]],gray]<.05&),{2},Heads->False]
]

GridPositions[grids[[3]],3]

TextGrid[Table[{n,grids[[n]],Length[pos=GridPositions[grids[[n]],n]],pos},{n,12}],Dividers->All]

l=Table[{{"Grid",{n,n}},{0,Missing["NotAvailable",Sort[GridPositions[grids[[n]],n]/.Thread[GraphData[{"Grid",{n,n}},"VertexCoordinates"]->Range[n^2]]]]}},{n,2,12}]

ConnectedDominatingSetQ[GraphData[#],#2[[2,2]]]&@@@l

PropertyReplace[l,"MinimumConnectedDominatingSets"]

RenameGraphFiles[]

Add configs for 3n×3n

SymmetricallyDistinctTallyGraphic["Grid",{9,9},10]

set1[n_]:=Union[Flatten[Table[{i,j},{i,n-2},{j,2,n,3}],1],Table[{n-1,j},{j,1,n}]]

Table[ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@set1[n]->1],{n,n}],Mesh->True],{n,9,19,3}]

set2[n_]:=Union[Flatten[Table[{i,j},{j,2,n,3},{i,n-If[j==2||j==n-1,0,2]}],1],Table[{n-1,j},{j,2,n-1}]]

Table[ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@set2[n]->1],{n,n}],Mesh->True],{n,9,19,3}]

set3[n_]:={#,n-#2+1}&@@@Union[Flatten[Table[{i,j},{j,2,n,3},{i,n-If[j==2,0,2]}],1],Table[{n-1,j},{j,3,n}]]

Table[ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@set3[n]->1],{n,n}],Mesh->True],{n,9,19,3}]

sets[n_]:=Union[Sort/@(Join@@(transformations[n,#]&/@{set1[n],set2[n],set3[n]}))]

emb[n_]:=GraphData[{"Grid",{n,n}},"VertexCoordinates"];

l=Table[{{"Grid",{n,n}},{0,Union[Sort/@(sets[n]/.Thread[emb[n]->Range[n^2]])]}},{n,9,20,3}]

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

Function[f,AllTrue[f[[2,2]],ConnectedDominatingSetQ[GraphData[f[[1]],#]]&]]@@@l

PropertyReplace[l,"MinimumConnectedDominatingSets"]

RenameGraphFiles[]

Figures

SymmetricallyDistinctTallyGraphic["Grid",Join[Range[6],Range[9,20,3]]]

SymmetricallyDistinctTallyGraphic["Grid",{7}]

Symmetric

Grid[
{
ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@#->1],{5,5}],Mesh->True,ImageSize->50,DataRange->{{1,5},{1,5}}],
#2,
FullSimplify@SymmetryTransformation[Point[#]]
}&@@@Normal[assoc],
Dividers->All,Alignment->Left]//Quiet

Grid[DeleteCases[
{
ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@#->1],{5,5}],Mesh->True,ImageSize->50,DataRange->{{1,5},{1,5}}],

#2,
FullSimplify@SymmetryTransformation[Point[#]]}&@@@Normal[assoc],
{_,_,TransformationGroup[{}]}
],Dividers->All,Alignment->Left]//Quiet

Table[ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@GraphData[{"Grid",{n,n}},"VertexCoordinates"][[Replace[GraphData[{"Grid",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]],Missing[_,l_List]:>l}]]]->1],{n,n}],Mesh->True,DataRange->{{1,n},{1,n}}],{n,2,12}]

Compute

Do[
Print[{gn=GraphData[{"Grid",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,Append[Range[7],9]}]

Do[
Print[{gn=GraphData[{"Grid",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,{8}}]

Grid n×n×n

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

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

Hanoi

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

HalvedCube

A382205

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

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

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

Helm

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

Hypercube

A382275

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

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

Keller

A381761

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

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

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

FindGeneratingFunction[DeleteMissing@seq,x]

SeriesCoefficient[((8 x (5+10092 x+5230169 (x^2)))/(((-1+x))^2)),{x,0,n}]

King m×n

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

King 2×n

seq=Table[GraphData[{"King",Sort[{2,n}]},"MinimumConnectedDominatingSetCount"],{n,10}]

Table[Piecewise[{{2,n==1},{4,n==2}},(2^(n-2))],{n,10}]

King n×n

A382206

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

Position[seq,4]//Flatten

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

One known

TextGrid[Table[
{
n,
If[ListQ[set=Replace[GraphData[{"King",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},l_List:>l[[1]]}]],Length@set,"?"],
set
},{n,20}],Dividers->All]

Configurations

image=Import["https://oeis.org/A370428/a370428_4.pdf"][[1]]

kingtiles=Flatten[ImagePartition[image,ImageDimensions[image]/{5,4}]]

kings=ImageCrop[ImageTake[ImageCrop[#],{30,-1}]]&/@kingtiles

king=ImageCrop@RemoveBackground@RemoveAlphaChannel@ImageCrop[ImageCrop[kings[[1]]],{180,210}]

bug(458317): ImageIdentify misclassifies certain objects and can be improved

ImageIdentify[king]

kings[[1]]

ImageContents[king]

ImageContents[kings[[4]]]

(Entity["black chess king", Entity["Character","U+265A"], "Entity[\"Character\", \"U+265A\"]", "character"])["Glyph"]//Graphics

ImagePosition[king,(Entity["black chess king", Entity["Character","U+265A"], "Entity[\"Character\", \"U+265A\"]", "character"])]

result=[largeImage=kings[[4]],subsetImage=king]

ImageCorrespondingPoints[kings[[1]],king]

ImageCorrespondingPoints[kings[[4]],king]

ImageCorrespondingPoints[kings[[4]],king,Method->"KAZE",KeypointStrength->0.001]

kings[[4]]

DominantColors[kings[[4]],MinColorDistance->.1]

kings[[7]]

Binarize@RemoveAlphaChannel@ColorReplace[kings[[7]],]

ImagePartition[Binarize@RemoveAlphaChannel@ColorReplace[kings[[7]],],{Round[ImageDimensions[kings[[7]]]/7]}]

KingPositions[kings[[8]],8]

MyImagePartition[img_,n_]:=Module[{width,height},
{width,height}=ImageDimensions[img];
Table[ImageTake[img,{i,i+1}width/n,{j,j+1}height/n],{i,0,n-1},{j,0,n-1}]
]

KingPositions[img_,n_]:=Module[
{
parts=Map[
ImageCrop[#,ImageDimensions[#]-3]&,
MyImagePartition[
Binarize@RemoveAlphaChannel@ColorReplace[kings[[n]],],
n
],
{2}
]
},
Position[ImageMeasurements[#,"Entropy"]&/@parts,_?(#>.5&)]
]

TextGrid[Table[{n,kings[[n]],Length[pos=KingPositions[kings[[n]],n]],pos},{n,20}],Dividers->All]

l=Table[{{"King",{n,n}},{0,Missing["NotAvailable",Sort[KingPositions[kings[[n]],n]/.Thread[GraphData[{"King",{n,n}},"VertexCoordinates"]->Range[n^2]]]]}},{n,10,16}]

ConnectedDominatingSetQ[GraphData[#],#2[[2,2]]]&@@@l

PropertyReplace[l,"MinimumConnectedDominatingSets"]

RenameGraphFiles[]

16x16 is known to have exactly 4, so compute them from the one known

king16pos=Union[Sort/@transformations[16,KingPositions[kings[[16]],16]]]

Length[%]

emb=GraphData[{"King",{16,16}},"VertexCoordinates"];

king16sets=Union[Sort/@(king16pos/.Thread[emb->Range[16^2]])]

AllTrue[king16sets,ConnectedDominatingSetQ[GraphData[{"King",{16,16}}],#]&]

With[{n=16},ArrayPlot[
SparseArray[Evaluate@Thread[Reverse/@emb[[#]]->1],{n,n}],Mesh->True,DataRange->{{0,n},{0,n}}]]&/@king16sets

l={
{{"King",{16,16}},{0,king16sets}}
}

PropertyReplace[l,"MinimumConnectedDominatingSets"]

RenameGraphFiles[]

Symmetric

data=Table[
{
ArrayPlot[SparseArray[Evaluate@Thread[(Reverse/@#)->1],{n,n}],Mesh->True,ImageSize->50,DataRange->{{0,n},{0,n}}],
#2,
If[Length[#]>1,Quiet[FullSimplify@SymmetryTransformation[Point[#]],{N::meprec}],Missing["OnePoint"]]
}&@@@Normal[
DistinctArrangementsWithTallies[
GraphData[{"King",{n,n}},"Graph","Grid"][[1]],
Which[
MissingQ[res=GraphData[{"King",{n,n}},"MinimumConnectedDominatingSets"]],
	res=Quiet[Import[FileNameJoin[{$GraphDataDirectory,"Properties","MinimumConnectedDominatingSets",GraphNameToFileName[{"King",{n,n}}]<>".gz"}]],{Import::nffil}],
ListQ[res],
	res,
True,
	{}]
]],{n,16}]

GraphicsRow[Cases[DeleteCases[data,_Counts],{_,1,_},∞][[All,1]],ImageSize->700]

GraphicsGrid[Partition[DeleteCases[DeleteCases[data,_Counts],{_,8,_},{2}][[All,All,1]]//Flatten,UpTo[5]],ImageSize->700]

Figures

SymmetricallyDistinctTallyGraphic["King",Range[7]]

SymmetricallyDistinctTallyGraphic["King",{8}]

SymmetricallyDistinctTallyGraphic["King",{16}]

7×7

Length[king7={}]

GraphData[{"King",{7,7}},"ConnectedDominationNumber"]

Length[sets=FindConnectedDominatingSet[GraphData[{"King",{7,7}}],{12},All,Debug->True,"KnownSets"->king7,Method->"LinearOptimization","Symmetry"->"Grid"]]//Timing

sets

With[{n=7},
Grid[
data={
ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@#->1],{n,n}],Mesh->True,ImageSize->50,DataRange->{{0,n},{0,n}}],
#2,
Quiet[FullSimplify@SymmetryTransformation[Point[#]],{N::meprec}]
}&@@@Normal[DistinctArrangementsWithTallies[GraphData[{"King",{n,n}}],sets]],
Dividers->All,Alignment->Left]
]

{Length[data],data[[All,2]]//Total,data[[All,2]]//Tally}

DeleteCases[data,{_,_,TransformationGroup[{}]}]//Column

Labeled[GraphicsGrid[Partition[Show[#,PlotLabel->#2]&@@@Reverse[data],UpTo[12]],ImageSize->1000],Style["7×7 king graph",14,Bold,FontFamily->"Times"],Top]

8×8

Length[kings8=]

AllTrue[kings8,ConnectedDominatingSetQ[GraphData[{"King",{8,8}}],#]&]

With[{n=8,sets=kings8},
Grid[
data={
ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@#->1],{n,n}],Mesh->True,ImageSize->50,DataRange->{{0,n},{0,n}}],
#2,
Quiet[FullSimplify@SymmetryTransformation[Point[#]],{N::meprec}]
}&@@@Normal[DistinctArrangementsWithTallies[GraphData[{"King",{n,n}}],sets]],
Dividers->All,Alignment->Left]]

DeleteCases[data,{_,_,TransformationGroup[{}]}]

{Length[data],data[[All,2]]//Total,data[[All,2]]//Tally}

90 8

GraphicsGrid[Partition[Show[#,PlotLabel->#2]&@@@data,UpTo[10]],ImageSize->1000]

Compute

Do[
Print[{
gn=GraphData[{"King",{n,n}},"#"],
FindConnectedDominatingSet[
GraphData[gn],
{GraphData[gn,"ConnectedDominationNumber"]},
All,
Method->"LinearOptimization",
"Symmetry"->"GroupOrbits"
]//Length//Timing
}],
{n,7}]

Knight m×n

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

Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumConnectedDominatingSetCount"],XXX}&/@GraphData["Knight"]]]

DeleteCases[%,{_,x_,x_}]

Knight n×n

A382207

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

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

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

One known

TextGrid[Table[
{
n,
If[ListQ[set=Replace[GraphData[{"Knight",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},Missing[_,l_List]:>l,l_List:>l[[1]]}]],Length@set,"?"],
set
},{n,20}],Dividers->All]

Figures

SymmetricallyDistinctTallyGraphic["Knight",{1,8}]

SymmetricallyDistinctTallyGraphic["Knight",{9}]

SymmetricallyDistinctTallyGraphic["Knight",{10},10]

Compute

Do[
Print[{gn=GraphData[{"Knight",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"SquareGrid"]//Length//Timing}],
{n,9}]

Do[
Print[{gn=GraphData[{"Knight",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,10}]

Do[
Print[{gn=GraphData[{"Knight",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,{10}}]

Ladder

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

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

Table[GraphData[{"Ladder",n},"MinimumConnectedDominatingSets"],{n,20}]

HighlightGraph[GraphData[{"Ladder",6}],#]&/@GraphData[{"Ladder",6},"MinimumConnectedDominatingSets"]

LadderRung

A000038

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

LindgrenSousselier

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

LuacsCube

A381729

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

MoebiusLadder

A005843

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

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

Mycielski

A381728

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

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

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

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

Odd

A382276

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

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

Pan

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

Path

A294619

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

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

PathComplement

A000217

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

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

Pell

A381755

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

Prism

A005893

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

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

FindSequenceFunction[Drop[seq,2],n-4]//Factor

Table[Piecewise[{{3,n==3},{30,n==4}},2(n^2+1)],{n,3,25}]

Queen n×n

A373394

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

Length@DeleteMissing@%

Agrees with A358062 (diagonal domination number) from 1–11 but differs at n==12 (d.d.n. == 8 but c.d.n. == 7)

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

Length@DeleteMissing@%

One known

GraphData[{"Queen",{12,12}},"MinimumConnectedDominatingSets"]

TextGrid[Table[
{
n,
If[ListQ[set=Replace[set0=GraphData[{"Queen",{n,n}},"MinimumConnectedDominatingSets"],{{}->{},Missing[_,l_List]:>l[[1]]}]],Length@set,"?"],
GraphData[{"Queen",{n,n}},"MinimumConnectedDominatingSetCount"],
Replace[set0,l_List:>l[[1]]]
},{n,20}],Dividers->All]

Figure

SymmetricallyDistinctTallyGraphic["Queen",Range[10],15]

SymmetricallyDistinctTallyGraphic["Queen",{11},15]

Compute

Do[
Print[{gn=GraphData[{"Queen",{n,n}},"#"],FindConnectedDominatingSet[GraphData[gn],{GraphData[gn,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]//Length//Timing}],
{n,9}]

Rook m×n

Block[{m,n},Sort[{{m,n}="Rook"/.GraphData[#,"NotationRules"],GraphData[#,"MinimumConnectedDominatingSetCount"],m^n+n^m-Min[m,n]!StirlingS2[Max[m,n],Min[m,n]]}&/@GraphData["Rook"]]]

DeleteCases[%,{_,x_,x_}]

Rook n×n

A103517

Inferred for n > 5:

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

GraphicsGrid[Flatten[Partition[#,UpTo[8]]&/@Table[With[{gn={"Rook",{n,n}}},Function[set,HighlightGraph[Annotate[GraphData[gn],VertexSize->{"Scaled",.03}],set]]/@GraphData[gn,"MinimumConnectedDominatingSets"]],{n,2,5}],1],ImageSize->800]

RookComplement n×n

A179058

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

GraphicsGrid[Flatten[Partition[#,UpTo[8]]&/@Table[With[{gn={"RookComplement",{n,n}}},Function[set,HighlightGraph[Annotate[GraphData[gn,"Graph"],VertexSize->{"Scaled",.03}],set]]/@GraphData[gn,"MinimumConnectedDominatingSets"]],{n,3,4}],1],ImageSize->800]

SierpinskiCarpet

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

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"MinimumConnectedDominatingSetCount"],{n,7}]

SierpinskiTetrahedron

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

Star

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

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

Sun

A001608

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

LinearRecurrence[{0,1,1},{3,2,5},20]

Sunlet

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

Tetrahedral

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

TorusGrid n×n

A382530

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

Transposition

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

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

Trapezohedron

A005843

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

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

Triangular

A373395

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

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

seq=Rest@Table[n(n-1)^(n-3),{n,2,20}]

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

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

TriangularGrid

A373393

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

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

Table[2(n-1),{n,0,10}]

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

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

GraphicsGrid[Flatten[Partition[#,UpTo[8]]&/@Table[Function[set,HighlightGraph[Annotate[GraphData[{"TriangularGrid",n}],VertexSize->{"Scaled",.03}],set]]/@GraphData[{"TriangularGrid",n},"MinimumConnectedDominatingSets"],{n,4}],1],ImageSize->800]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

A132609

Inferred for n > 8:

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

seq=Table[Piecewise[{{1,n==1}},Sum[(n-k)^(k-1) k^(n-k-1),{k,n-1}]],{n,20}]

Sum[(n-k)^(k-1) k^(n-k-1),{k,n-1}]

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

TriangularHoneycombObtuseKnight

A380859

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

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

TriangularHoneycombQueen

A381722

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

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

Grid[DeleteCases[Table[
{
n,
sets=GraphData[{"TriangularHoneycombQueen",n},"MinimumConnectedDominatingSets"],
HighlightGraph[GraphData[{"TriangularHoneycombQueen",n},"Graph","TriangularGrid"][[1]],#,VertexSize->Medium]&/@sets
},{n,2,20,2}],{_,_Missing,_}],Dividers->All]

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

98/14

14 7

72/12

Prepend[Accumulate[Range[9,14]],0]

29+69

Binomial[Ceiling[12/2]+1,2]

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

HighlightGraph[GraphData[#,"Graph","TriangularGrid"][[1]],#2,VertexSize->Medium,ImageSize->Medium]&@@@rules

TriangularHoneycombRook

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

Web

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

Wheel

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

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

WhiteBishop n×n

A381727

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

seq==Join[{2,4},Table[Sum[(((2k))^(n-2k-2)) (((n-2k-1))^(2 k-1)),{k,Floor[n/2]-1}],{n,4,20}]]

FindSequenceFunction[Drop[BFileSequence[381727],2],n-2]//Head//Timing

FindGeneratingFunction[BFileSequence[381727],x]//Head//Timing

FullSimplify[n^(k-1)k^(n-1)/.{n->n-1-2k,k->2k}]

Sum[(2^(-2-2 k+n)) (k^(-2-2 k+n)) (((-1-2 k+n))^(-1+2 k)),{k,Floor[n/2]-1}]

Algorithms

set=FindConnectedDominatingSet[g=GraphData[{"Grid",{4,4}}]]

aut=GraphAutomorphismGroup[g]

orbits=GroupOrbits[aut,{set}][[1]]

emb=GraphEmbedding[g];

ArrayPlot[SparseArray[Evaluate@Thread[Reverse/@emb[[#]]->1],{4,4}],Mesh->True,ImageSize->50,DataRange->{{0,4},{0,4}}]&/@orbits

set=FindConnectedDominatingSet[g=GraphData[{"Grid",{4,4}}]]

aut=GraphAutomorphismGroup[g]

GroupOrbits[aut,{set}]

<<MathWorld`Graphs`

cdn=GraphData[{"Grid",{5,5}},"ConnectedDominationNumber"]

Binomial[5^2,11]

l0=FindConnectedDominatingSet[g=GraphData[{"Grid",{5,5}}],{cdn},All,Debug->True];//Timing

l1=FindConnectedDominatingSet[g=GraphData[{"Grid",{5,5}}],{cdn},All,Debug->True,Method->"LinearOptimization"];//Timing

l2=FindConnectedDominatingSet[g=GraphData[{"Grid",{5,5}}],{cdn},All,Debug->True,Method->"LinearOptimization","Symmetry"->"Grid"];//Timing

l1===l2

l3=FindConnectedDominatingSet[g=GraphData[{"Grid",{5,5}}],{cdn},All,Debug->True,Method->"LinearOptimization","Symmetry"->"GroupOrbits"];//Timing

l3===l1

Check

<<MathWorld`Graphs`

DeleteCases[Monitor[{
gn=#,
GraphData[#,"MinimumConnectedDominatingSetCount"],Length[FindConnectedDominatingSet[GraphData[#],{GraphData[#,"ConnectedDominationNumber"]},All,Method->"Subsets"]]
}&/@GraphData["Connected",;;8],gn],
{_,x_,x_}]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"MinimumConnectedDominatingSetCount"],Length[FindConnectedDominatingSet[GraphData[#],{GraphData[#,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->None]]
}&/@GraphData["Connected",;;8],gn],
{_,x_,x_}]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"MinimumConnectedDominatingSetCount"],Length[FindConnectedDominatingSet[GraphData[#],{GraphData[#,"ConnectedDominationNumber"]},All,Method->"LinearOptimization","Symmetry"->"GroupOrbits"]]
}&/@GraphData["Connected",;;8],gn],
{_,x_,x_}]//Timing

FindConnectedDominatingSet[GraphData["BullGraph"],Automatic,All,Method->"LinearOptimization","Symmetry"->"GroupOrbits",Debug->True]

GroupOrbits[GraphAutomorphismGroup[GraphData["BullGraph"]],{{4,5}}]