Connected Dominating Set

Author

Eric W. Weisstein
March 7, 2025

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

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

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

Count table

GraphDataCountTable["ConnectedDominatingSetCount",{"Alkane"->000302,"Andrasfai"->287429,"Antiprism"->286986,"Apollonian"->298105,"Barbell"->000302,"Bishop"->7,"BlackBishop"->289145,"Book"->242985,"Bruhat"->317481,"Camel"->000007,"Centipede"->000079,"CocktailParty"->289254,"Complete"->225,"CompleteBipartite"->060867,"CompleteTripartite"->291703,"CrossedPrism"->287430,"Crown"->287471,"Cycle"->005408,"CycleComplement"->347477,"DiagonalIntersection"->300527,"Dipyramid"->381790,"Empty"->7,"DoubleCone"->000302,"FibonacciCube"->298115,"FoldedCube"->298114,"Gear"->287431,{"Grid",2}->287690,{"Grid",3}->381797,"HalvedCube"->288987,"Hanoi"->373441,"Hypercube"->291704,"King"->289180,"Knight"->291705,"Ladder"->291706,"LucasCube"->370573,"MoebiusLadder"->287005,"Mycielski"->287432,"Pan"->008586,"Path"->113311,"PathComplement"->302689,"Pell"->381789,"PlummerToft"->381791,"Prism"->286985,"Queen"->289185,"Rook"->289196,"RookComplement"->290949,"SierpinskiGasket"->373442,"Star"->000079,"Sun"->087131,"Sunlet"->000079,"TorusGrid"->298106,"Transposition"->291707,"Trapezohedron"->381794,"Triangular"->298104,"TriangularGrid"->288721,"TriangularHoneycombAcuteKnight"->7,"TriangularHoneycombBishop"->381795,"TriangularHoneycombObtuseKnight"->381796,"TriangularHoneycombQueen"->289865,"TriangularHoneycombRook"->7,"TriangularSnake"->000079,"Web"->000302,"Wheel"->176691,"WheelComplement"->000004,"WhiteBishop"->289169}]

Paramertrized families

<<MathWorld`Graphs`

Andrasfai

A287429

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

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

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

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

Antiprism

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

A286986

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

Apollonian

A298105

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

(PARI) \\ here t0..t3 are for 0..3 outside vertices included in set.
D(t0, t1, t2, t3)={[t1^3, t1*t2^2, t1^2*t2 + t2^2*t3, t2^3 + t3^3]}
a(n)={my(v=[1, 2, 2, 2]); for(i=2, n, v=D(v[1], v[2], v[3], v[4])); v[1]+3*v[2]+3*v[3]+v[4]}

seq={1,3,3,1}.#&/@NestList[Function[{t0,t1,t2,t3},{t1^3,t1 t2^2,t1^2t2+t2^2t3,t2^3+t3^3}]@@#&,{1,2,2,2},7]

FindLinearRecurrence[seq]//Head//Timing

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

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

BananaTree

GraphData[{"BananaTree",{3,6}},"Graph","Labeled"]

GraphData[{"BananaTree",{3,6}},"ConnectedDominatingSets"]

Position[VertexDegree[GraphData[{"BananaTree",{3,6}}]],_?(#>1&)]//Flatten

GraphData[{"BananaTree",{2,7}},"Graph","Labeled"]

GraphData[{"BananaTree",{2,7}},"ConnectedDominatingSets"]

Position[VertexDegree[GraphData[{"BananaTree",{2,7}}]],_?(#>1&)]//Flatten

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

GraphData["BananaTree"]

Select[GraphData["BananaTree"],GraphData[#,"ConnectedDominatingSets"]===Missing["NotAvailable"]&]

Bishop n×n

A000007

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

BlackBishop n×n

A289145

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

Bruhat

A317481

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

Camel n×n

A000007

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

Centipede

A000079

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

gf=x FindGeneratingFunction[seq,x]

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

CocktailParty

A289254

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

FindSequenceFunction[seq,n]

Complete

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

A000225

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

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

n×n×n

2 (1+(2^n)) (((-1+(2^(1+n))))^2)

seq=Table[{GraphData[{"CompleteTripartite",{k,m,n}},"ConnectedDominatingSetCount"],((2^k)-1)((2^m)-1)((2^n)-1)},{n,10},{m,n},{k,m}]

CompleteTripartite n×n×n

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

A291703

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

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

Table[Piecewise[{{7,n==1}},2 ((2^(n-1))+1) ((((2^n)-1))^2)],{n,20}]

FullSimplify[2 ((2^(n-1))+1) ((((2^n)-1))^2)]

Table[Piecewise[{{7,n==1}},2-3 (2^n)+(8^n)],{n,20}]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

seq=CoefficientList[Series[((-7+23 x-78 (x^2)+48 (x^3))/(-1+11 x-26 (x^2)+16 (x^3))),{x,0,50}],x]

FindLinearRecurrence[DeleteMissing@Drop[seq,1]]

Join[{7},LinearRecurrence[{11,-26,16},{54,490,4050},20]]

CrossedPrism

A287430

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

seq={115,1063,9121,75607,611569,4857223,38034241,294475447,2258978449,17196401383,130059675361,978211787287,7322040929329,54576195433543,405286730532481,2999780651211127,22137879320864209,162941058582753703,1196418733436205601};

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

Join[{115},Table[(7^(n-3)) (343+240 n),{n,3,20}]]

FindLinearRecurrence[Rest@seq]

LinearRecurrence[{14,-49},{115,1063},20]

gf=x FindGeneratingFunction[seq,x]

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

Crown

A287471

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

FindLinearRecurrence[seq]

CubeConnectedCycle

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

Cycle

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

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

DiagonalIntersection

A300527

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

Dipyramid

A381790

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

FindSequenceFunction[seq,n-2]//FullSimplify

seq=Table[3 2^n+2n-2,{n,0,32}]

StringLength[ToString[seq]]

coef=FindLinearRecurrence[seq]

OEISRecurrenceString[coef]

OEISRecurrenceIndexString[coef]

LinearRecurrence[{4,-5,2},{6,14,28},{0,20}]

gf=FindGeneratingFunction[seq,x]

OEISGeneratingFunctionString[gf,x]

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

DoubleCone

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

FindSequenceFunction[seq,n-2]//FullSimplify

DutchWindmill

GraphData[{"DutchWindmill",{2,4}},"Graph","Labeled"]

GraphData[{"DutchWindmill",{3,5}},"Graph","Labeled"]

GraphData[{"DutchWindmill",{3,5}},"ConnectedDominatingSets"]

Position[VertexDegree[GraphData[{"BananaTree",{3,6}}]],_?(#>1&)]//Flatten

GraphData[{"DutchWindmill",{4,6}},"Graph","Labeled"]

GraphData[{"DutchWindmill",{4,6}},"ConnectedDominatingSets"]

Position[VertexDegree[GraphData[{"BananaTree",{2,7}}]],_?(#>1&)]//Flatten

Block[{m,n},DeleteCases[{
#,
{m,n}="DutchWindmill"/.GraphData[#,"NotationRules"];If[n==3,1,m Floor[(n-1)/2]+1],
GraphData[#,"ConnectedDominationNumber"]
}&/@GraphData["DutchWindmill"],{_,x_,x_}]]

GraphData["DutchWindmill"]

Select[GraphData["DutchWindmill"],GraphData[#,"ConnectedDominatingSets"]===Missing["NotAvailable"]&]

Empty

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

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

FibonacciCube

A298115

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

FoldedCube

A298114

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

Grid m×n

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

A291872

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

data=Import["https://oeis.org/A291872/b291872.txt","Table"][[All,2]];

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]//Column

Grid n×n

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

A287690

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

Grid k×m×n

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

seq=Table[GraphData[{"Grid",{n,n,n}},"ConnectedDominatingSetCount"],{n,10},{m,n},{k,m}]

Grid n×n×n

A381797

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

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

HalvedCube

A288987

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

Hanoi

A373441

seq=Table[GraphData[{"Hanoi",n},"ConnectedDominatingSetCount"],{n,6}]

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

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

Hypercube

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

A291704

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

Keller

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

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

King m×n

A291873

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

data=Import["https://oeis.org/A291873/b291873.txt","Table"][[All,2]];

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]//Column

King n×n

A289180

seq=Table[GraphData[{"King",{n,n}},"ConnectedDominatingSetCount"],{n,10}]

seq={1,15,336,29648,11293568,17784998912,113637188081536,2924018436019899392,301641905727809350974464,124378420721322865523465096192,204571358406088229163099037060664832,1340178778197906145868721021815647098466816};

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Knight m×n

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

seq=Table[GraphData[{"Knight",{m,n}},"ConnectedDominatingSetCount"],{n,10},{m,n}]//Column

Knight n×n

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

A291705

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

Ladder

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

A291706

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

gf=x FindGeneratingFunction[DeleteCases[seq,_Missing],x]

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

seq=Table[Piecewise[{{3^n,n==1||n==2}},4LucasL[n-1,2]],{n,30}]

FindLinearRecurrence[Drop[seq,2]]

Join[{3,9},LinearRecurrence[{2,1},{24,56},20]]

FindSequenceFunction[Drop[DeleteCases[seq,_Missing],2],n]//FullSimplify

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

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

LadderRung

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

LucasCube

A370573

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

Do[Print[{n,FindLinearRecurrence[Drop[DeleteMissing@seq,n]]//Head//Timing}],{n,0,4}]

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

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

MengerSponge

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

MoebiusLadder

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

A287005

Inferred for n > 14:

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

Do[Print[{n,FindLinearRecurrence[Drop[DeleteMissing@seq,n]]//Head//Timing}],{n,0,4}]

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

Table[-1+(((1-(Sqrt[2])))^n)+(((1+(Sqrt[2])))^n)+(2+(((1+(Sqrt[2])))^n) (-5+4 (Sqrt[2]))-(((1-(Sqrt[2])))^n) (5+4 (Sqrt[2]))) n,{n,20}]//Expand

A002203

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

Table[LucasL[n,2],{n,5}]

Table[(((1+(Sqrt[2])))^n) (-5+4 (Sqrt[2]))-(((1-(Sqrt[2])))^n) (5+4 (Sqrt[2])),{n,20}]//Expand

Table[(((1+(Sqrt[2])))^n) (-5+4 (Sqrt[2]))-(((1-(Sqrt[2])))^n) (5+4 (Sqrt[2])),{n,20}]//Expand

Table[-5((((1+(Sqrt[2])))^n) +(((1-(Sqrt[2])))^n))+4(Sqrt[2])((((1+(Sqrt[2])))^n) -(((1-(Sqrt[2])))^n)), {n,20}]//Expand

A000129

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

Table[-5LucasL[n,2]+16Fibonacci[n,2], {n,20}]//Expand

Table[-1+LucasL[n,2]+(2-5LucasL[n,2]+16Fibonacci[n,2]) n, {n,20}]//Expand

Table[(-5n+1)LucasL[n,2]+(2+16Fibonacci[n,2]) n-1, {n,20}]//Expand

seq=Table[(1-5n)LucasL[n,2]+2(8Fibonacci[n,2]+1) n-1, {n,28}]//Expand

ToString[seq,InputForm]//StringLength

gf=x FullSimplify[FindGeneratingFunction[DeleteMissing[seq],x]]//Factor

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

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

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

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{6,-11,4,5,-2,-1},{9,13,49,129,361,989},20]

Mycielski

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

A287432

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

Odd

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

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

Path

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

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

PathComplement

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

FindSequenceFunction[seq,n]

FindLinearRecurrence[Drop[seq,1]]

gf=x FindGeneratingFunction[seq,x]

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

Pell

A381789

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

PlummerToft

A381791

seq=Table[GraphData[{"PlummerToft",n},"ConnectedDominatingSetCount"],{n,20}]

FindSequenceFunction[Rest@seq,n-1]

seq=Table[2 (4+17 (2^(-1+n))),{n,0,30}]

StringLength[ToString[seq]]

coef=FindLinearRecurrence[seq]

LinearRecurrence[{3,-2},{42,76},{0,20}]

OEISRecurrenceString[coef]

OEISRecurrenceIndexString[coef]

gf=FindGeneratingFunction[seq,x]

OEISGeneratingFunctionString[gf,x]

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

Prism

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

A286985

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

seq={7,7,39,115,343,967,2663,7203,19239,50887,133543,348179,902775,2329607,5986535,15327555,39115847,99532423,252601127,639548595,1615746455,4073951559,10253517671,25763632995,64635943783,161928486727,405134009511,1012371656275};

coef=FindLinearRecurrence[seq]

Length@coef

Take[seq,6]

LinearRecurrence[{6,-11,4,5,-2,-1},{7,7,39,115,343,967},20]

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

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

Table[LucasL[n,2],{n,10}]

Table[((((1+(Sqrt[2])))^n) (-5+4 (Sqrt[2]))-(((1-(Sqrt[2])))^n) (5+4 (Sqrt[2]))),{n,10}]//Expand

%14/2

Table[3Fibonacci[n-2,2]+Fibonacci[n-1,2],{n,10}]

Table[1+LucasL[n,2]+n(-2+2(3Fibonacci[n-2,2]+Fibonacci[n-1,2])),{n,20}]//Expand

FullSimplify[1+LucasL[n,2]+n(-2+2(3Fibonacci[n-2,2]+Fibonacci[n-1,2]))]

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

gf=x FindGeneratingFunction[seq,x]

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

Queen n×n

A289185

seq=Table[GraphData[{"Queen",{n,n}},"ConnectedDominatingSetCount"],{n,10}]

Rook n×n

A289196

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

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

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

b[m_,n_]:=Sum[(-1)^j Binomial[m,j](2^(m-j)-1)^n,{j,0,m}]

b[m,n]

T[_,1]=T[1,_]=1;
T[m_,n_]:=T[m,n]=b[m,n]-Sum[T[i,j]b[m-i,n-j]Binomial[m-1,i-1]Binomial[n,j],{i,m-1},{j,n-1}];

a[n_]:=T[n,n]+2Sum[Binomial[n,k]T[n,k],{k,n-1}]

Array[a,20]

RookComplement n×n

A290949

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

-3 ((Binomial[n, 2])^2)-2 ((((2^(n-1))-1))^2) (n^2)+(((n-1))^2) (n^2)+(n^2)+(2^(n^2))-2 ((2^n)-1) n-1

Table[If[n==1,1,2^(n^2)-2n(2^n-1)+n^2-2n^2(2^(n-1)-1)^2+n^2(n-1)^2-3Binomial[n,2]^2-1],{n,20}]

-3 ((Binomial[n, 2])^2)-2 ((((2^(n-1))-1))^2) (n^2)+(((n-1))^2) (n^2)+(n^2)+(2^(n^2))-2 ((2^n)-1) n-1

FullSimplify[2^(n^2)-2n(2^n-1)+n^2-2n^2(2^(n-1)-1)^2+n^2(n-1)^2-3Binomial[n,2]^2-1]

seq=Table[If[n==1,1,2^(n^2)-2n(2^n-1)+n^2(1-2(2^(n-1)-1)^2+(n-1)^2)-3Binomial[n,2]^2-1],{n,50}];

-3 ((Binomial[n, 2])^2)+(-2 ((((2^(n-1))-1))^2)+(((n-1))^2)+1) (n^2)+(2^(n^2))-2 ((2^n)-1) n-1

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

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

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

SierpinskiCarpet

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

SierpinskiSieve

A373442

seq=Table[GraphData[{"SierpinskiSieve",n},"ConnectedDominatingSetCount"],{n,7}]

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

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

SierpinskiTetrahedron

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

Star

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

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

FindLinearRecurrence[Drop[seq,2]]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

gf=x FindGeneratingFunction[seq,x]

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

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

Sun

A087131

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[(2^n)LucasL[n],{n,3,20}]

Sunlet

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

FindSequenceFunction[seq,n-2]

Tetrahedral

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

TorusGrid m×n

Table[GraphData[{"TorusGrid",{m,n}},"ConnectedDominatingSetCount"],{n,3,10},{m,3,n}]//Column

TorusGrid n×n

A298106

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

Trapezohedron

A381794

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

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

Do[Print[{n,FindLinearRecurrence[Drop[DeleteMissing@seq,n]]//Head//Timing}],{n,0,4}]

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

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

Triangular

A298104

seq=Table[GraphData[{"Triangular",n},"ConnectedDominatingSetCount"],{n,2,10}]

A001187 = Number of connected labeled graphs with n nodes.

Sum[2^Binomial[n,2] x^n/n!,{n,0,∞}]

Sum[2^Binomial[n,2] x^n/n!,{n,0,∞}]

Sum[2^Binomial[n,2] x^n/n!,{n,0,k}]

g=Sum[2^Binomial[n,2] x^n/n!,{n,0,20}]

Range[0,20]! CoefficientList[Series[Log[g]+1,{x,0,20}],x]

Clear[a]

a[n_]:=a[n]=(2^(Binomial[n,2]))-Sum[k Binomial[n,k]2^((n-k)(n-k-1)/2)a[k],{k,n-1}]/n

a(n) = A001187(n) + n*A001187(n-1) for n > 2.

seq=Join[{1},Table[a[n]+n a[n-1],{n,3,20}]]

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

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

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

seq=Table[a[n]+n a[n-1],{n,3,150}];

Head[coef=FindLinearRecurrence[seq]]//Timing

seq=Table[a[n]+n a[n-1],{n,3,200}];

Head[coef=FindLinearRecurrence[seq]]//Timing

TriangularGrid

A288721

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

seq={1,7,32,296,5744,227080,18084720,2883751336,916819998880,579403471332808,726271886301488352,1802717127912019473096,8849500619057758939673040,85830556827312530479498758296,1643431935596454045971815328866560,62082178562357221739454020443666212184};

FindLinearRecurrence[Rest@seq]

gf=FindGeneratingFunction[seq,x]

FindSequenceFunction[seq,n+1]

TriangularHoneycombBishop

A381795

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

TriangularHoneycombObtuseKnight

A381796

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

TriangularHoneycombQueen

A289865

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

Transposition

A291707

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

Wheel

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

A176691

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

FindSequenceFunction[DeleteCases[seq,_Missing],n-3]//FullSimplify

gf=FindGeneratingFunction[Table[2^n+2 n+1,{n,0,60}],x]

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

WhiteBishop n×n

A289169

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

Algorithms

SelectFirst

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

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

Loop

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

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

Tree

g=GraphData[gn="ForkGraph","Graph","Labeled"]

set=GraphData[gn,"MinimumConnectedDominatingSets"]

pick=Position[VertexDegree[g],_?(#>1&),1]//Flatten

HighlightGraph[g,pick]

g=GraphData[gn={"Firecracker",{5,8}},"Graph","Labeled"]

set=GraphData[gn,"ConnectedDominatingSets"][[2]]

pick=Position[VertexDegree[g],_?(#>1&),1]//Flatten

HighlightGraph[g,set]

GraphData[#,"MinimumConnectedDominatingSetCount"]&/@GraphData["Tree"]//Tally

Select[GraphData["Tree"],GraphData[#,"MinimumConnectedDominatingSetCount"]===2&]