Domatic Number

Author

Eric W. Weisstein
May 10, 2019

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

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

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

Counts

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

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","DomaticNumber"}]]))//Column

Union/@values//Column

A294206

Flatten[tallies]

A000088

Total/@tallies

Shifted by 1:

tallies[[All,1]]

Length/@tallies

Not in OEIS:

Total/@values

Missing

DateString[]

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

Length[missing]

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

Parametrized families

Andrasfai

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

Table[Piecewise[{{2,n==1||n==2}},n-1],{n,10}]

Antiprism

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

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

Table[Piecewise[{{3,n==3},{5,Mod[n,5]==0}},4],{n,3,20}]

%==seq

Apollonian

seq=Table[GraphData[{"Apollonian",n},"DomaticNumber"],{n,5}]

Not d.p.:

Table[Floor[Divide@@GraphData[{"Apollonian",n},{"VertexCount","DominationNumber"}]],{n,5}]

Barbell

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

Bishop n×n

Probably n-1 for n > 2

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

Table[Floor[Divide@@GraphData[{"Bishop",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

BlackBishop n×n

Probably 3 for n >= 6

seq=Table[GraphData[{"BlackBishop",{n,n}},"DomaticNumber"],{n,10}]

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

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

Table[Floor[Divide@@GraphData[{"BlackBishop",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

Book

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

Centipede

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

CocktailParty

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

Complete

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

Table[GraphData[{"Complete",n},"DomaticNumber"],{n,20}]

Table[DomaticNumber[g=System`CompleteGraph[n],FindDominatingSet[g,Infinity,All]],{n,5}]

CompleteBipartite m×n

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

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

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

CompleteBipartite n×n

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

CompleteTripartite k×m×n

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

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

DeleteCases[Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Piecewise[{{3,k==m==n==1},{Floor[3n/2],k==m==n},{XXX,k==m||m==n||n==k}},k+m+n-Max[k,m,n]]}&/@GraphData["CompleteTripartite"]]],{_,x_,x_}]

Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Floor[Divide@@GraphData[#,{"VertexCount","DominationNumber"}]]}&/@GraphData["CompleteTripartite"]]]

CompleteTripartite n×n×n

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

Domatically perfect for n > 1

Checked up to n==7, inferred for 8–10

A032766

Table[GraphData[{"CompleteTripartite",{n,n,n}},"DomaticNumber"],{n,10}]

Table[DomaticNumber[g=System`CompleteGraph[{n,n,n}],FindDominatingSet[g,Infinity,All]],{n,3}]

Table[Floor[Divide@@GraphData[{"CompleteTripartite",{n,n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

Simplify[Floor[Divide@@Entity["Graph",{"CompleteTripartite",{n,n,n}}][{"VertexCount","DominationNumber"}]],n>1]

Table[Piecewise[{{3,n==1}},Floor[((3 n)/2)]],{n,10}]

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

Possibly 4 for n >= 4

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

Table[GraphData[{"CubeConnectedCycle",n},"DominatingSetCount"],{n,3,8}]

Table[GraphData[{"CubeConnectedCycle",n},"MinimalDominatingSetCount"],{n,3,8}]

Table[Floor[Divide@@GraphData[{"CubeConnectedCycle",n},{"VertexCount","DominationNumber"}]],{n,3,8}]

Simplify[Floor[Divide@@Entity["Graph",{"CubeConnectedCycle",n}][{"VertexCount","DominationNumber"}]],n>1]

Cycle

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

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

System`CycleGraph[5,VertexLabels->"Name"]

Table[DomaticNumber[g=System`CycleGraph[n],FindDominatingSet[g,Infinity,All]],{n,3,10}]

Table[Piecewise[{{3,Mod[n,3]==0}},2],{n,3,30}]

FindSequenceFunction[%,n-2]//Simplify

FullSimplify[2+(2/3)(Cos[n Pi 2/3]+1/2)]

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

Table[Ceiling[7(n+1)/3]-Ceiling[7n/3],{n,3,20}]

Empty

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

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

g=System`Graph[{1,2},{},VertexLabels->"Name"]

(ds=FindDominatingSet[g,Infinity,All])

FindDominatingSet[System`Graph[{1,2,3},{}],Infinity,All]

Table[DomaticNumber[System`Graph[Range[n],{}],{Range[n]}],{n,5}]

FibonacciCube

Possibly 3 for n >= 5

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

Gear

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

GeneralizedPetersen

Entity["Graph",{"GeneralizedPetersen",{n,k}}]["DomaticNumber"]

Possibly domatically perfect for k!=2

dp=Block[{n,k},Sort[{{n,k}="GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Floor[Divide@@GraphData[#,{"VertexCount","DominationNumber"}]]}&/@GraphData["GeneralizedPetersen"]]]

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

Cases[dp,{_,x_,x_}][[All,1]]

Grid m×n

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

Grid n×n

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

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

Table[GraphData[{"Grid",{n,n}},"DominatingSetCount"],{n,10}]

Table[GraphData[{"Grid",{n,n}},"MinimalDominatingSetCount"],{n,10}]

Not d.p. fpr n==4

Table[Floor[Divide@@GraphData[{"Grid",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

With[{n=3},DomaticNumber[g=System`GridGraph[{n,n}],FindDominatingSet[g,Infinity,All],Debug->True]]

System`GridGraph[{4,4},VertexLabels->"Name"]

Table[DomaticNumber[g=System`GridGraph[{n,n}],FindDominatingSet[g,Infinity,All]],{n,3}]

Grid k×m×n

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

Grid n×n×n

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

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

Table[GraphData[{"Grid",{n,n,n}},"DominatingSetCount"],{n,10}]

Table[GraphData[{"Grid",{n,n,n}},"MinimalDominatingSetCount"],{n,10}]

Table[Floor[Divide@@GraphData[{"Grid",{n,n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

HalvedCube

Likely perfectly domatic

A290128

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

Table[Floor[Divide@@GraphData[{"HalvedCube",n},{"VertexCount","DominationNumber"}]],{n,10}]

Helm

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

Hypercube

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

Possibly domatically perfect?

A157887

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

Table[Floor[Divide@@GraphData[{"Hypercube",n},{"VertexCount","DominationNumber"}]],{n,0,10}]

Floor[Divide@@Entity["Graph",{"Hypercube",n}][{"VertexCount","DominationNumber"}]]

HypercubeGraph[4,VertexLabels->"Name"]

It is known that a(n)=n+1 when n is of the form 2^k-1, and a(n)<n+1 otherwise, a(n) is weakly increasing, and a(nm-1)>=a(n-1)a(m-1).

Table[DomaticNumber[g=HypercubeGraph[n],FindDominatingSet[g,Infinity,All]],{n,3}]

Keller

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

Probably (4^(n-1))

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

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

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

Table[Floor[Divide@@GraphData[{"Keller",n},{"VertexCount","DominationNumber"}]],{n,5}]

King n×n

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

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

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

Table[Floor[Divide@@GraphData[{"King",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

Knight m×n

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

DeleteCases[Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Piecewise[{{1,Min[m,n]==1||m==n==2||m==n==3||(Min[m,n]==2&&Max[m,n]==3)},{2,Min[m,n]==2}},3]}&/@GraphData["Knight"]]],{_,x_,x_}]

Knight n×n

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

Simplify[Piecewise[{{1,Min[m,n]==1||m==n==2||m==n==3||(Min[m,n]==2&&Max[m,n]==3)},{2,Min[m,n]==2}},3],m==n]

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

Table[GraphData[{"Knight",{n,n}},"DominatingSetCount"],{n,10}]

Table[GraphData[{"Knight",{n,n}},"MinimalDominatingSetCount"],{n,10}]

Table[Floor[Divide@@GraphData[{"Knight",{n,n}},{"VertexCount","DominationNumber"}]],{n,10}]

Ladder

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

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

Table[LadderGraph[n,VertexLabels->"Name"],{n,6}]

Monitor[Table[DomaticNumber[g=LadderGraph[n]],{n,6}],n]//Timing

LadderRung

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

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

MengerSponge

Possibly 3 for n >= 2

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

MoebiusLadder

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

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

Table[Piecewise[{{2,n==4},{4,Mod[n,4]==2}},3],{n,3,20}]

Mycielski

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

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

Table[Piecewise[{{2,n==3||n==4},{4,n==5}},n],{n,11}]

%==seq

Do[Print[{n,DomaticNumber[GraphData[{"Mycielski",n}]]//Timing}],{n,4}]

Table[GraphData[{"Mycielski",n},"DominatingSetCount"],{n,11}]

Table[GraphData[{"Mycielski",n},"MinimalDominatingSetCount"],{n,11}]

Table[Floor[Divide@@GraphData[{"Mycielski",n},{"VertexCount","DominationNumber"}]],{n,10}]

Odd

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

Possibly 4 for n >= 4

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

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

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

Table[Floor[Divide@@GraphData[{"Odd",n},{"VertexCount","DominationNumber"}]],{n,7}]

Pan

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

Path

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

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

Table[DomaticNumber[g=PathGraph[Range[n]],FindDominatingSet[g,Infinity,All]],{n,8}]

Prism

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

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

Table[PrismGraph[n,VertexLabels->"Name"],{n,3,4}]

Table[Piecewise[{{4,Mod[n,4]==0}},3],{n,3,25}]

Do[Print[{n,DomaticNumber[PrismGraph[n]]//Timing}],{n,3,5}]

Queen m×n

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

Queen n×n

A292192

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

Table[Floor[Divide@@GraphData[{"Queen",{n,n}},{"VertexCount","DominationNumber"}]],{n,7}]

Rook m×n

Block[{m,n},Sort[{{m,n}="Rook"/.GraphData[#,"NotationRules"],GraphData[#,"DomaticNumber"],Max[m,n]}&/@GraphData["Rook"]]]

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

Rook n×n

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

RookComplement n×n

Possibly A000212 for n >= 3

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

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

SierpinskiCarpet

Probably 3 for n >= 2

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

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

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

Table[Floor[Divide@@GraphData[{"SierpinskiCarpet",n},{"VertexCount","DominationNumber"}]],{n,4}]

SierpinskiGasket

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

Table[Floor[Divide@@GraphData[{"SierpinskiSieve",n},{"VertexCount","DominationNumber"}]],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"DomaticNumber"],{n,5}]

Star

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

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

Sun

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

Sunlet

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

Transposition

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

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

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

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

Table[Floor[Divide@@GraphData[{"Transposition",n},{"VertexCount","DominationNumber"}]],{n,6}]

Triangular

Computed to be domatically perfect for n<=7; inferred for the remainder

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

Table[Floor[Divide@@GraphData[{"Triangular",n},{"VertexCount","DominationNumber"}]],{n,2,20}]

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

Table[GraphData[{"TriangularHoneycombBishop",n},"DominatingSetCount"],{n,9}]

Table[GraphData[{"TriangularHoneycombBishop",n},"MinimalDominatingSetCount"],{n,9}]

Table[Floor[Divide@@GraphData[{"TriangularHoneycombBishop",n},{"VertexCount","DominationNumber"}]],{n,9}]

TriangularHoneycombObtuseKnight

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

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"DominatingSetCount"],{n,9}]

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"MinimalDominatingSetCount"],{n,9}]

Table[Floor[Divide@@GraphData[{"TriangularHoneycombBishop",n},{"VertexCount","DominationNumber"}]],{n,9}]

TriangularHoneycombQueen

domatically perfect

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"DomaticNumber"],{n,10}]

Table[GraphData[{"TriangularHoneycombQueen",n},"DominatingSetCount"],{n,10}]

Table[GraphData[{"TriangularHoneycombQueen",n},"MinimalDominatingSetCount"],{n,10}]

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

Table[Floor[Divide@@GraphData[{"TriangularHoneycombQueen",n},{"VertexCount","DominationNumber"}]],{n,9}]

TriangularHoneycombRook

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

Web

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

Wheel

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

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

Table[Piecewise[{{4,Mod[n,3]==1}},3],{n,4,20}]

System`WheelGraph[5,VertexLabels->"Name"]

Table[DomaticNumber[g=System`WheelGraph[n],FindDominatingSet[g,Infinity,All]],{n,4,7}]

WhiteBishop n×n

Looks like alternating 3 and n-1

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

Table[GraphData[{"WhiteBishop",{n,n}},"DominatingSetCount"],{n,2,10}]

Table[GraphData[{"WhiteBishop",{n,n}},"MinimalDominatingSetCount"],{n,2,10}]

Table[Floor[Divide@@GraphData[{"WhiteBishop",{n,n}},{"VertexCount","DominationNumber"}]],{n,2,10}]

Algorithm

DomaticNumber1[g_System`Graph,opts___?OptionQ]:=DomaticNumber1[g,FindDominatingSet[g,Infinity,All],opts]

DomaticNumber1[g_System`Graph,dom_List,opts___?OptionQ]:=Module[{v=Sort[VertexList[g]],dm,d=Min[VertexDegree[g]]+1,domaticpartition,debug=Debug/.{opts}/.Debug->False},
While[
If[debug,Print[d]];
((domaticpartition=SelectFirst[Subsets[dom,{d}],Sort[Join@@#]===v&,False])===False),
d--
];
If[debug,Print[domaticpartition]];
d
]

d1=Monitor[DomaticNumber1[g=GraphData[gn=#],FindDominatingSet[g,Infinity,All]]&/@GraphData[;;6],gn];//Timing

Pre-check compatible lengths (slower)

DomaticNumber2[g_System`Graph,dom_List,opts___?OptionQ]:=Module[{v=Sort[VertexList[g]],dm,d=Min[VertexDegree[g]]+1,domaticpartition,debug=Debug/.{opts}/.Debug->False,n=VertexCount[g]},
While[
If[debug,Print[d]];
((domaticpartition=SelectFirst[Subsets[dom,{d}],Total[Length/@#]===n&&Sort[Join@@#]===v&,False])===False),
d--
];
If[debug,Print[domaticpartition]];
d
]

d2=Monitor[DomaticNumber2[g=GraphData[gn=#],FindDominatingSet[g,Infinity,All]]&/@GraphData[;;6],gn];//Timing

d1==d2

FindIndependentVertexSet

Using idea of Stan

We want the largest possible collection of disjoint dom. sets. That is the defn. of the domatic number. 
So given G, make the derived graph G1 whose verts are the dom sets with an edge between two with nonempty intersection.

The any family of disjoint dominating sets of G corresponds exactly to an ind. set in G1. So the largest ind set in G1 is the largest family of disjoint dom sets.

Here, the dominating sets can be just the minimal ones, and the sets returned (even if *all* dominating sets are returned) are minimal (that can be extended to be a full cover).

FindMaximumDomaticPartition[g_System`Graph]:=FindMaximumDomaticPartition[g,FindDominatingSet[g,Infinity,All]]

FindMaximumDomaticPartition[g_System`Graph,dom_List]:=Module[{edges,gi,onecoloring},
edges=Select[Subsets[dom,{2}],IntersectingQ@@#&];
gi=System`Graph[dom,UndirectedEdge@@@edges];
FindIndependentVertexSet[gi][[1]]
]

DomaticNumber[g_System`Graph,opts___?OptionQ]:=DomaticNumber[g,FindDominatingSet[g,Infinity,All],opts]

DomaticNumber[g_System`Graph,dom_List,opts___?OptionQ]:=Length[FindMaximumDomaticPartition[g,dom,opts]]

DomaticNumber[System`CompleteGraph[4]]

DomaticNumber3[System`CompleteGraph[4]]

DomaticNumber3[System`CompleteGraph[3]]

FindMaximumDomaticPartition[GraphData[{5,31}]]

DomaticNumber[GraphData[{5,31}]]

FrobeniusSolve

IntegerPartitions[5]

(ds=FindDominatingSet[g=System`CompleteGraph[{4,4}],Infinity,All])//Length

Min[VertexDegree[g]]+1

Tally[Length/@ds]

lens=%[[All,1]]

FrobeniusSolve[lens,5]

CirculantGraph[6,{2,3}]

g=System`CirculantGraph[6,{2,3},VertexLabels->"Name"]

(ds=FindDominatingSet[g,Infinity,All])//Length

ds

DomaticNumber[g,ds]

Table[Binomial[51,d],{d,4}]

Compare

Graphs/@Range[6];

(dom2=DomaticNumber[#,FindDominatingSet[#,Infinity,All]]&/@Graphs[6])//Timing

(dom3=DomaticNumber[#,MinimalSets@FindDominatingSet[#,Infinity,All]]&/@Graphs[6])//Timing

dom2==dom1==dom3