Dominating Unique Graph

Author

Eric W. Weisstein
August 12, 2025

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

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

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

Classes

GraphClassesThatAre["DominatingUnique"]

Counts

UniquePolynomialCount[n_,prop_]:=Module[
{
file=FileNameJoin[{$GraphDataDirectory,"Nodes",prop,prop<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}],
lines
},
Count[Length/@Split[Sort[ReadList[file,"String",NullRecords->True]]],1]
]

A378516: Dominating unique

(unique=Table[UniquePolynomialCount[n,"DominationPolynomial"],{n,10}])//Timing

Length/@Table[GraphData["DominatingUnique",n],{n,8}]

Take[unique,8]-%

A378517: Dominating nonunique

nonunique=Table[SimpleGraphCount[n],{n,Length[unique]}]-unique

Length/@Table[GraphData["DominatingNonunique",n],{n,8}]

Take[nonunique,8]-%

Figure

(unique=Table[GraphData["DominatingUnique",n],{n,4}])//Column

Length/@unique

bug(454882): GraphicsGrid's fail to display thin graphs, change width of rows, and display grid element content suboptimally starting in V14.1

GraphicsGrid[
Map[StyleGraphs[Annotate[GraphData[#],{PlotLabel->If[MissingQ[not=GraphData[#,"Notation"]],
Style[GraphData[#,"Name"],Directive[FontFamily->"Times",LightDarkSwitched@Black,16,Italic]],
Style[not/.c_String?(StringMatchQ[LetterCharacter]):>Style[c,Italic]/.Row[r_]:>Row[r," "],Directive[FontFamily->"Times",LightDarkSwitched@Black,16]]
],ImageSize->{200,200}}],VertexSize->If[#==="SingletonGraph",.015,{"Scaled",.05}]]&,
Flatten[Partition[#,UpTo[5]]&/@unique,1],
{2}],
Dividers->{{Thick,{True},Thick},{Thick,Thick,Thick,Thick,True,Thick}},
Alignment->Top,ImageSize->500]

GraphDataCountTable

<<MathWorld`Graphs`

GraphDataCountTable["DominatingUnique"]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"DominatingUnique"],{n,10}]

Table[GraphData[{"Alkane",n},"CodominatingGraphNames"],{n,10}]//Column

AlternatingGroupGraph

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

Andrasfai

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

Table[GraphData[{"Andrasfai",n},"CodominatingGraphNames"],{n,20}]//Column

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"DominatingUnique"],{n,20}]

Antiprism

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

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

Apollonian

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

Table[GraphData[{"Apollonian",n},"CodominatingGraphNames"],{n,5}]//Column

Barbell

Inferred (2(Subscript[K, n])) for n > 10:

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

Table[Cases[GraphData[{"Barbell",n},"CodominatingGraphNames"],"2C3"|_String?(StringMatchQ["2K*"])],{n,3,20}]//Column

GraphData[{"Barbell",10},"DominationPolynomial"][x]

GraphData["2K10","DominationPolynomial"][x]

Bishop n×n

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

Table[GraphData[{"Bishop",{n,n}},"CodominatingGraphNames"],{n,20}]//Column

BlackBishop n×n

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

Table[GraphData[{"BlackBishop",{n,n}},"CodominatingGraphNames"],{n,20}]//Column

Book

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

Table[GraphData[{"Book",n},"CodominatingGraphNames"],{n,20}]//Column

Table[GraphData[{"Book",n},"CodominatingGraphs"],{n,20}]//Column

Bruhat

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

Camel n×n

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

Centipede

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

CocktailParty

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

Complete

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

Inferred for n > 10:

seq=Table[GraphData[{"Complete",n},"DominatingUnique"],{n,30}]

CompleteBipartite n×n

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

Inferred False with codominating graph ({"Rook", {2, n}}) for n > 10:

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

Table[GraphData[{"CompleteBipartite",{n,n}},"CodominatingGraphNames"],{n,20}]//Column

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"DominatingUnique"],
Missing["NotAvailable"]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

Table[GraphData[{"CompleteTripartite",{n,n,n}},"CodominatingGraphNames"],{n,10}]//Column

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"DominatingUnique"],
Missing["NotAvailable"]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"DominatingUnique"],{n,2,12}]

Crown

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

CubeConnectedCycle

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

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

Cycle

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

Inferred for n > 10:

seq=Table[GraphData[{"Cycle",n},"DominatingUnique"],{n,3,30}]

CycleComplement

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

Table[GraphData[{"CycleComplement",n},"CodominatingGraphNames"],{n,3,20}]//Column

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

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

DoubleCone

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

Empty

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

Inferred for n > 10:

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

FibonacciCube

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

Fiveleaper n×n

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

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"DominatingUnique"],{n,20}]

Goldberg

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

Grid n×n

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

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

Table[GraphData[{"Grid",{n,n}},"CodominatingGraphNames"],{n,20}]//Column

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"DominatingUnique"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"DominatingUnique"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

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

Table[GraphData[{"Hanoi",n},"CodominatingGraphNames"],{n,6}]//Column

Helm

Inferred False with {"Spoke", {n, 2}} for n > 5:

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

Table[GraphData[{"Helm",n},"CodominatingGraphNames"],{n,3,20}]//Column

Table[Subtract@@(DominationPolynomial[#,x]&/@{HelmGraph[n],SpokeGraph[n,2]}),{n,3,9}]//Timing

Hypercube

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

Inferred True for n > 3:

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

Keller

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

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

King n×n

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

Table[GraphData[{"King",{n,n}},"CodominatingGraphNames"],{n,20}]//Column

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"DominatingUnique"],
Missing["NotAvailable"]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"DominatingUnique"],
Missing["NotAvailable"]
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

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

Table[GraphData[{"Ladder",n},"CodominatingGraphNames"],{n,20}]//Column

Table[GraphData[{"Ladder",n},"CodominatingGraphs"],{n,20}]//Column

LadderRung

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

Inferred nE, nP4, {"Centipede", ...}, {"Sunlet", ...}:

Table[GraphData[{"LadderRung",n},"CodominatingGraphNames"],{n,20}]//Column

DominationPolynomial[GraphData["4P4"],x]

DominationPolynomial[GraphData[{"Sunlet",8}],x]

DominationPolynomial[GraphData[{"Centipede",8}],x]

LindgrenSousselier

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

LucasCube

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

MengerSponge

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

MoebiusLadder

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

Inferred False for n = 17, 19, ..., 25 (codominating with {"Prism", n}:

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

Table[GraphData[{"MoebiusLadder",n},"CodominatingGraphNames"],{n,3,25}]//Column

GraphData[{"MoebiusLadder",15},"DominationPolynomial"][x]

GraphData[{"Prism",15},"DominationPolynomial"][x]

Mycielski

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

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

Odd

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

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

Pan

Inferred True for n > 9:

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

Path

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

Inferred False for n > 10 (codominating with cycle + 2 adjacent pendant vertices):

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

Table[GraphData[{"Path",n},"CodominatingGraphNames"],{n,20}]//Column

Table[GraphData[{"Path",n},"CodominatingGraphs"],{n,20}]//Column

CycleGraphWithTwoPendantVertices[n_]:=Module[{v=CirclePoints[Csc[Pi/n]/2,n],ee=Sort[Sort/@Join[Partition[Range[n],2,1,1],{{1,n+1},{n,n+2}}]]},
v=Join[v,{v[[1]]+{1,0},v[[-1]]-{1,0}}];
Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]]

CycleGraphWithTwoPendantVertices[6]

DominationPolynomial[%,x]

GraphData["P8","DominationPolynomial"][x]

CycleGraphWithTwoPendantVertices[10]

DominationPolynomial[%,x]

GraphData["P12","DominationPolynomial"][x]

PathComplement

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

Pell

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

PlummerToft

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

Prism

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

Codominating with MoebiusLadder for odd n:

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

Table[GraphData[{"Prism",n},"CodominatingGraphNames"],{n,3,25}]//Column

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"DominatingUnique"],{n,5}]

Table[GraphData[{"Spoke",{n,n}},"CodominatingGraphNames"],{n,5}]//Column

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"DominatingUnique"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"DominatingUnique"],{n,3,5}]

Star

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

Inferred for n > 10:

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

Sun

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

Table[GraphData[{"Sun",n},"CodominatingGraphNames"],{n,3,20}]//Column

Sunlet

Cochromatic with Centipede, LadderRung, nE, nP4, etc.

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

Table[GraphData[{"Sunlet",n},"CodominatingGraphNames"],{n,3,20}]//Column

Tetrahedral

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

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"DominatingUnique"],{n,3,20}]

Transposition

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

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

Trapezohedron

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

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

Triangular

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

Table[GraphData[{"Triangular",n},"CodominatingGraphNames"],{n,2,20}]//Column

GraphData[{"Triangular",6},"DominationPolynomial"][x]

GraphData[{"TriangularHoneycombQueen",5},"DominationPolynomial"][x]

GraphData[{"Triangular",7},"DominationPolynomial"][x]

GraphData[{"TriangularHoneycombQueen",6},"DominationPolynomial"][x]

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"DominatingUnique"],{n,1,20,2}]

Web

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

Table[GraphData[{"Web",n},"CodominatingGraphNames"],{n,3,20}]//Column

Wheel

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

Inferred for n > 10:

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

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"DominatingUnique"],{n,4,20}]

Table[GraphData[{"WheelComplement",n},"CodominatingGraphNames"],{n,4,20}]//Column

Table[GraphData[{"WheelComplement",n},"CodominatingGraphs"],{n,4,20}]//Column

WhiteBishop n×n

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

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"DominatingUnique"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"DominatingUnique"],{n,20}]

GraphData

GraphDataClassString

GraphDataClassString["DominatingUnique"]