Distiguishing Number

Author

Eric W. Weisstein
September 14, 2024

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

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

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

Sources

https://arxiv.org/pdf/math/0406542.pdf

https : // arxiv.org/pdf/1707.06161.pdf

Theorems

https://arxiv.org/pdf/math/0406542.pdf

Corollary 2.14. (Albertson, Collins, and Kleitman) A graph G with |Aut(G)| ≤ k! has distinguishing number D(G) ≤ k.

The distinguishing number of a graph must be the same as the distinguishing number of its complement,

First we observe that D(G) = 1 if and only if G is an identity graph, i.e., one whose automorphism group is trivial.

The complexity of deciding if a given graph has a non-trivial automorphism has not been settled [9, 11].It is known to be Turing equivalent to Unique Graph Isomorphism, and is a candidate for a problem whose difficulty lies between being in P and being NP ¡ complete. Hence determining if D(G) = 1 may be difficult.

Labelings

Take[DeleteCases[SortBy[Select[GraphData[All],GraphData[#,"MinimumDistinguishingLabelings"]===Missing["NotAvailable"]&],GraphData[#,"V"]&],{"Complete"|"CompleteBipartite"|"CompleteTripartite"|"Empty",_}],500]

Special cases

MinimumDistinguishingLabelings[GraphData["TriangleSquare"]]

GraphDataCountTable

GraphDataCountTable["DistinguishingNumber"]

Parametrized families

<<MathWorld`Graphs`

Alkane

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

Floor/@InverseFactorial/@Table[GraphData[{"Alkane",n},"|Aut|"],{n,10}]

Do[Print[{gn=GraphData[{"Alkane",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,10}];

AlternatingGroupGraph

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

Andrasfai

Inferred for n > 10:

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

Antelope n×n

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

Antiprism

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

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

Do[Print[{n,DistinguishingNumber[AntiprismGraph[n]]//Timing}],{n,4,20}]

Apollonian

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

Barbell

Inferred for n > 6:

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

Do[Print[{gn=GraphData[{"Barbell",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,3,10}];

Bishop n×n

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

BlackBishop n×n

Inferred for n  > 7:

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

Do[Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,8}];

Book

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

Bruhat

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

Camel n×n

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

Centipede

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

CocktailParty

Likely 4 for n > 3:

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

Length@DeleteMissing@seq

Do[Print[{gn=GraphData[{"CocktailParty",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,10}];

Complete

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

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

Do[Print[{n,DistinguishingNumber[CompleteGraph[n]]//Timing}],{n,7}]

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

Table[n!,{n,20}]

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

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

Do[Print[{n,DistinguishingNumber[CompleteGraph[{n,n}]]//Timing}],{n,6}]

Table[GraphData[{"CompleteBipartite",{n,n}},"MinimumDistinguishingLabelingCount"],{n,10}]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

CrossedPrism

Inferred for n > 14:

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

Do[Print[{gn=GraphData[{"CrossedPrism",2n},"#"],DistinguishingNumber[GraphData[gn],Debug->True,Method->"PermutationList"]//Timing}],{n,2,10}];

Crown

LIkely 3 for n>3

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

Length@DeleteMissing@seq

CubeConnectedCycle

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

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

Cycle

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

Table[GraphData[{"Cycle",n},"DistinguishingNumber"],{n,3,30}]

Table[DistinguishingNumber[CycleGraph[n]],{n,3,10}]

Table[GraphData[{"Cycle",n},"MinimumDistinguishingLabelingCount"],{n,3,20}]

FindSequenceFunction[{12,28,96,252,600,1364,3048,6552,13804,29040},n]

FindGeneratingFunction[{252,600,1364,3048,6552,13804,29040},x]

C3

DistinguishingQ[CycleGraph[3],#]&/@Or@@Tuples[Range[2],3]

DistinguishingQ[CycleGraph[3],#]&/@Or@@Tuples[Range[3],3]

DistinguishingNumber[CycleGraph[3]]

tuples=Tuples[Range[3],3];
perms=PermutationList[#,3]&/@Rest[GroupElements[GraphAutomorphismGroup[CycleGraph[3]]]];
min=Pick[tuples,Function[phi,SameQ[phi,phi[[#]]]&/@Or@@perms]/@tuples]

MinimumDistinguishingLabelings[CycleGraph[3]]

Tuples[{1,2},3]

C4

DistinguishingLabelingQ[CycleGraph[4],#]&/@Or@@Tuples[Range[2],4]

DistinguishingLabelingQ[CycleGraph[4],#]&/@Or@@Tuples[Range[3],4]

MinimumDistinguishingLabelings[CycleGraph[4]]

C5

DistinguishingNumberQ[CycleGraph[5],Debug->True]

DistinguishingQ[CycleGraph[5],#]&/@Or@@Tuples[Range[2],5]

DistinguishingQ[CycleGraph[5],#]&/@Or@@Tuples[Range[3],5]

MinimumDistinguishingLabelings[CycleGraph[5]]

C6

DistinguishingNumberQ[CycleGraph[6],Debug->True]

DistinguishingQ[CycleGraph[6],#]&/@Or@@Tuples[Range[2],6]

DistinguishingQ[CycleGraph[6],#]&/@Or@@Tuples[Range[3],6]

MinimumDistinguishingLabelings[CycleGraph[6]]

CycleComplement

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

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

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

DoubleCone

Inferred for n > 11:

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

Empty

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

Table[GraphData[{"Empty",n},"DistinguishingNumber"],{n,30}]

Do[Print[{n,DistinguishingNumber[Graph[Range[n],{}]]//Timing}],{n,7}]

Table[GraphData[{"Empty",n},"MinimumDistinguishingLabelingCount"],{n,20}]

Table[n!,{n,20}]

FibonacciCube

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

Fiveleaper n×n

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

Flower

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

FoldedCube

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

Gear

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

GeneralizedPetersen

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

DeleteCases[Block[{n,k},{#,{n,k}="GeneralizedPetersen"/.GraphData[#,"NotationRules"];Piecewise[{{3,{n,k}=={4,1}||{n,k}=={5,2}}},2],
GraphData[{"GeneralizedPetersen",{n,k}},"DistinguishingNumber"]}]&/@GraphData["GeneralizedPetersen"],{_,x_,x_}]

Giraffe n×n

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

Goldberg

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

Grid n×n

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

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

Grid m×n

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

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

Grid n×n×n

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

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

Grid k×m×n

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

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

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

Table[GraphData[{"Hypercube",n},"DistinguishingNumber"],{n,0,10}]

Do[Print[{n,DistinguishingNumber[GraphData[{"Hypercube",n}]]//Timing}],{n,7}]

Identity

data=GraphData[#,{"#","Identity","DistinguishingNumber"}]&/@GraphData[All];

Cases[data,{_,True,Except[1]}]

Cases[data,{_,Except[True],1}]

Keller

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

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

King n×n

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

King m×n

Entity["Graph",{"King",{m,n}}]["DistinguishingNumber"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"DistinguishingNumber"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

Table[GraphData[{"Knight",{n,n}},"DistinguishingNumber"],{n,20}]

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"DistinguishingNumber"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

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

LadderRung

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

LucasCube

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

MengerSponge

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

MengerSponge

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

MiddleLayer

seq=Table[GraphData[{"MiddleLayer",n},"DistinguishingNumber"],{n,5}]

Do[Print[{gn=GraphData[{"MiddleLayer",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,4}];

MoebiusLadder

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

Table[GraphData[{"MoebiusLadder",n},"DistinguishingNumber"],{n,3,25}]

Mycielski

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

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

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,6}];

Odd

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

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

Pan

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

Path

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

Table[GraphData[{"Path",n},"DistinguishingNumber"],{n,10}]

Do[Print[{n,DistinguishingNumber[PathGraph[Range[n]]]//Timing}],{n,10}]

DistinguishingNumber[GraphData["P3"]]

MinimumDistinguishingLabelings[GraphData["P3"]]

A233411

Do[Print[{n,Length@MinimumDistinguishingLabelings[PathGraph[Range[n]]]//Timing}],{n,20}]

Table[GraphData[{"Path",n},"MinimumDistinguishingLabelingCount"],{n,2,10}]

FullSimplify[FindSequenceFunction[{2,4,12,24,56,112,240,480,992},n-1],n∈Integers&&n>0]

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

Table[2^n-2^Ceiling[n/2],{n,2,10}]

FindGeneratingFunction[{2,4,12,24,56,112,240,480,992},x]//Factor

PathComplement

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

Pell

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

PlummerToft

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

Prism

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

Table[GraphData[{"Prism",n},"DistinguishingNumber"],{n,3,25}]

Queen n×n

Possibly 2 for n > 2:

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

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,8}];

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"DistinguishingNumber"],{n,3}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"DistinguishingNumber"],{n,5}]

SierpinskiTetrahedron

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

Spoke n×n

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

Do[Print[{gn=GraphData[{"Spoke",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,5}];

StackedBook

Inferred for n > 4:

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

Do[Print[{gn=GraphData[{"StackedBook",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,8}];

StackedPrism

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

Star

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

Table[GraphData[{"Star",n},"DistinguishingNumber"],{n,25}]

ToEntity/@Table[CompleteGraph[{n,1}],{n,5}]

Do[Print[{n,DistinguishingNumber[GraphData[{"Star",n}]]//Timing}],{n,7}]

A001563(n+1)

Table[GraphData[{"Star",n},"MinimumDistinguishingLabelingCount"],{n,10}]

FindSequenceFunction[{4,18,96,600,4320},n]

Table[(n-1)(n-1)!,{n,3,10}]

Table[n n!,{n,0,3}]

a(2)=4 is m.d.l. count for S3

Sun

Table[GraphData[{"Sun",n},"DistinguishingNumber"],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"DistinguishingNumber"],{n,3,20}]

Tetrahedral

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

TorusGrid n×n

Inferred for n > 5:

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

Do[Print[{gn=GraphData[{"TorusGrid",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,3,8}];

Transposition

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

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

Trapezohedron

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

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

Triangular

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

In section 5 we sketch an argument due to Lovasz that for n>=6, D(L(Kn)) = 2.

ToEntity/@Table[LineGraph[CompleteGraph[n]],{n,2,6}]

Do[Print[{n,DistinguishingNumber[LineGraph[CompleteGraph[n]]]//Timing}],{n,7}]

Table[GraphData[{"Triangular",n},"MinimumDistinguishingLabelingCount"],{n,3,10}]

TriangularGrid

Inferred for n > 6:

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

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,8}];

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"DistinguishingNumber"],{n,20}]

TriangularSnake

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

Web

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

Wheel

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

Table[GraphData[{"Wheel",n},"DistinguishingNumber"],{n,4,20}]

Do[Print[{n,DistinguishingNumber[GraphData[{"Wheel",n}]]//Timing}],{n,4,10}]

Table[GraphData[{"Wheel",n},"MinimumDistinguishingLabelingCount"],{n,4,20}]

FindSequenceFunction[{24,56,192,504,1200,2728,6096,13104,27608,58080,119040},n]

FindGeneratingFunction[{24,56,192,504,1200,2728,6096,13104,27608,58080,119040},x]

WheelComplement

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

WhiteBishop n×n

Inferred for n > 7:

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

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],DistinguishingNumber[GraphData[gn],Debug->False,Method->"PermutationList"]//Timing}],{n,2,8}];

Zebra n×n

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

Disconnected

DeleteCases[Function[g,{g,GraphData[g,"DistinguishingNumber"],Max[GraphData[#,"DistinguishingNumber"]&/@GraphData[g,"ConnectedComponents","Name"]]}]/@GraphData["Disconnected",;;7],{_,x_,x_}]

Grid[Function[g,{g,GraphData[g,"V"],GraphData[g,"C"],GraphData[#,"DistinguishingNumber"]&/@GraphData[g,"ConnectedComponentGraphs","Name"],GraphData[g,"DistinguishingNumber"]}]/@GraphData["Disconnected",;;6],Alignment->Left,Dividers->All]

GraphData[{4,2},"ConnectedComponentGraphs","Name"]

GraphData[#,"DistinguishingNumber"]&/@%

GraphData[{4,3},"ConnectedComponentGraphs","Name"]

GraphData[#,"DistinguishingNumber"]&/@%

GraphData["TriangleSquare","ConnectedComponentGraphs","Name"]

GraphData[#,"DistinguishingNumber"]&/@%

GraphData["TriangleSquare","DistinguishingNumber"]

GraphData["TwoSquares","DistinguishingNumber"]

GraphData["SquareGraph","DistinguishingNumber"]

Checks

DeleteCases[Monitor[{gn=#,GraphData[#,"DistinguishingNumber"],DistinguishingNumber[GraphData[#]]}&/@GraphData[;;7],gn],
{_,x_,x_}]//Timing

DeleteCases[Monitor[{gn=#,GraphData[#,"DistinguishingNumber"],DistinguishingNumber[GraphData[#]]}&/@GraphData[;;8],gn],
{_,x_,x_}]//Timing