Hamming Graph

Author

Eric W. Weisstein
November 27, 2023

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

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

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

Figure

hamming=Cases[GraphData["Hamming"],{"Hamming",_}]

GraphicsGrid[
Partition[
Show[With[{g=GraphData[#]},StyleGraphs[#,VertexSize->{"Scaled",.02}]&@If[Lookup[Options[g],GraphLayout]===None,Annotate[g,GraphLayout->"SpringElectricalEmbedding"],g]],PlotLabel->Style[Row[{H,"(",Sequence@@Riffle[#[[2]],", "],")"}],Directive[14,Black,FontFamily->"Times"]]]&/@hamming,
UpTo[4]
],Dividers->All,Alignment->Center,ImageSize->700]

Properties

Integral

GraphData["Hamming","Integral"]

Classes

TableForm[{ham="Hamming"/.GraphData[#,"NotationRules"],#,RecognizeGraph[HammingGraph@@ham]}&/@
GraphData["Hamming"],TableDepth->2]

TableForm[Flatten[Table[{{d,q},rg=RecognizeGraph[HammingGraph[d,q]],If[rg==={},{},"Hamming"/.GraphData[rg,"NotationRules"]]},{d,4},{q,7}],1],TableDepth->2]

Enumeration

H(2,n)

RecognizeGraph/@Table[HammingGraph[2,n],{n,5}]

Diameter/@Table[HammingGraph[2,n],{n,5}]

H(3,n)

RecognizeGraph/@Table[HammingGraph[3,n],{n,5}]

H(4,n)

RecognizeGraph/@Table[HammingGraph[4,n],{n,5}]

H(5,n)

RecognizeGraph/@Table[HammingGraph[5,n],{n,3}]

H(6,n)

RecognizeGraph/@Table[HammingGraph[6,n],{n,3}]

H(d,1)

RecognizeGraph/@Table[HammingGraph[n,1],{n,2,7}]

H(d,2)

RecognizeGraph/@Table[HammingGraph[n,2],{n,2,7}]

H(d,3)

RecognizeGraph/@Table[HammingGraph[n,3],{n,2,7}]

RecognizeGraph/@Table[UndirectedGraph[CayleyGraph[AbelianGroup[Table[3,{n}]]]],{n,6}]

Embeddings

<<MathWorld`Graphs`

{"Hamming", {3, 3}}

Names

GraphData[{"Hamming",{3,3}},"StandardName"]

GraphData[{"Hamming",{3,3}},"StandardNames"]

Primary

GraphData[{"Hamming",{3,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Hamming",{3,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Hamming",{3,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Hamming",{3,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Hamming",{3,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Hamming",{3,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Hamming",{3,3}},"Graph","Degenerate"]

Perspective

GraphData[{"Hamming",{3,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Hamming",{3,3}},"Polyhedron"]

Bilateral

GraphData[{"Hamming",{3,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Hamming",{3,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Hamming",{3,3}},"Planar"]

GraphData[{"Hamming",{3,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{3,3}},{"RCN","CN"}]

GraphData[{"Hamming",{3,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],TimeConstraint->3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Hamming",{3,3}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,3}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Hamming",{3,3}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Hamming",{3,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Hamming",{3,3}},"Circulant"]

GraphData[{"Hamming",{3,3}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Hamming",{3,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"Hamming",{3,3}},"Line"]

LineGraphQ[GraphData[{"Hamming",{3,3}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Hamming",{3,3}}&]

RootGraph[GraphData[{"Hamming",{3,3}}]]

Halin

GraphData[{"Hamming",{3,3}},"Halin"]

GraphData[{"Hamming",{3,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Hamming",{3,3}},"Rigid"]

GraphData[{"Hamming",{3,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Hamming",{3,3}},"Flexible"]

GraphData[{"Hamming",{3,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,3}},"LCF"]

GraphData[{"Hamming",{3,3}},"HamiltonianCycleCount"]

GraphData[{"Hamming",{3,3}},"LCFSignature"]

GraphData[{"Hamming",{3,3}},"LCFNotations"]

GraphData[{"Hamming",{3,3}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Hamming",{3,3}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

NiceLCFGraphs[LCFNotation/@{,,,,,,},4,3]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Hamming",{3,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Hamming",{3,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Hamming",{3,3}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"Hamming",{3,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,3}}],Debug->True]//Timing

GraphData[{"Hamming",{3,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{3,3}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{3,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{3,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{3,3}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

gs={RotateGraph[,{97,314}],RotateGraph[,{137,198}]}

UnitDistance construction Vertex-Edge-Degenerate Gebracht

GraphData[{"Hamming",{3,3}},"Graph","All"][[-1]]

DegenerateGraphEmbeddingTypes[%]

E. Gebracht, May 2008

Embedding due to E. Gerbracht, May 2008

Here's the graph. 9/1 +  9/2 + 9/4.

g3=LinesToGraph[,.1,10^8.]

GraphPlot[g3,Method->None,ImageSize->200]

Vertices[g3]

Degrees[g3]//Union

Vertices[g3]

V[g3]

RecognizeGraph[g3]

GraphData[{"Hamming",{3,3}},"ChromaticNumber"]

ShowLabeledGraph[g3]

Mean/@Map[Norm,#[[All,2]]&/@Split[Sort[{Norm[#],#}&/@Vertices[g3]],Abs[#1[[1]]-#2[[1]]]<.01&],{2}]

FullForm[%]

RootApproximant/@%

Norm/@(Subtract@@@(Edges[g3]/.n_Integer:>Vertices[g3][[n]]))

r=RootApproximant[Vertices[g3],2,Method->{"DegreeCost"->1}];

Norm/@(Subtract@@@(Edges[g3]/.n_Integer:>r[[n]]))//N

Graph[{"Hamming",{3,3}}]//InputForm

g=Graph[{{{1, 2}}, {{1, 3}}, {{1, 4}}, {{1, 7}}, {{1, 10}}, {{1, 19}}, {{2, 3}}, {{2, 5}}, {{2, 8}}, {{2, 11}}, {{2, 20}}, {{3, 6}}, 
  {{3, 9}}, {{3, 12}}, {{3, 21}}, {{4, 5}}, {{4, 6}}, {{4, 7}}, {{4, 13}}, {{4, 22}}, {{5, 6}}, {{5, 8}}, {{5, 14}}, {{5, 23}}, 
  {{6, 9}}, {{6, 15}}, {{6, 24}}, {{7, 8}}, {{7, 9}}, {{7, 16}}, {{7, 25}}, {{8, 9}}, {{8, 17}}, {{8, 26}}, {{9, 18}}, {{9, 27}}, 
  {{10, 11}}, {{10, 12}}, {{10, 13}}, {{10, 16}}, {{10, 19}}, {{11, 12}}, {{11, 14}}, {{11, 17}}, {{11, 20}}, {{12, 15}}, 
  {{12, 18}}, {{12, 21}}, {{13, 14}}, {{13, 15}}, {{13, 16}}, {{13, 22}}, {{14, 15}}, {{14, 17}}, {{14, 23}}, {{15, 18}}, 
  {{15, 24}}, {{16, 17}}, {{16, 18}}, {{16, 25}}, {{17, 18}}, {{17, 26}}, {{18, 27}}, {{19, 20}}, {{19, 21}}, {{19, 22}}, 
  {{19, 25}}, {{20, 21}}, {{20, 23}}, {{20, 26}}, {{21, 24}}, {{21, 27}}, {{22, 23}}, {{22, 24}}, {{22, 25}}, {{23, 24}}, 
  {{23, 26}}, {{24, 27}}, {{25, 26}}, {{25, 27}}, {{26, 27}}}, {{{-1.4619, 0.}}, {{-1.1199, -0.9397}}, {{-1.1199, 0.9397}}, 
  {{-0.7779, 0.}}, {{-0.5959, -0.5}}, {{-0.5959, 0.5}}, {{-0.4771, -0.1736}}, {{-0.4771, 0.1736}}, {{-0.2539, -1.4397}}, 
  {{-0.2539, -0.4397}}, {{-0.2539, 0.4397}}, {{-0.2539, 1.4397}}, {{-0.1351, -0.766}}, {{-0.1351, 0.766}}, {{0.0882, -0.5}}, 
  {{0.0882, 0.5}}, {{0.3889, -0.6736}}, {{0.3889, -0.3264}}, {{0.3889, 0.3264}}, {{0.3889, 0.6736}}, {{0.5077, 0.}}, 
  {{0.731, -1.266}}, {{0.731, -0.266}}, {{0.731, 0.266}}, {{0.731, 1.266}}, {{1.3737, -0.5}}, {{1.3737, 0.5}}}];

unit=GraphData[{"Hamming",{3,3}},"Graph","UnitDistance"][[1]]

v=GraphData[gn={"Hamming",{3,3}},"Embeddings","UnitDistance"][[1]]

EuclideanDistance@@@(GraphData[gn,"Edges","List"]/.i_Integer:>v[[i]])

gs=GraphData[{"Hamming",{3,3}},"Graph",{"Labeled","Degenerate"}]

GraphData[{"Hamming",{3,3}},"Edges"]

DegenerateEmbeddingQ/@gs

Tally[%]

UnitDistance construction Pegg = Gebracht?

Pegg Cuic Root comp pros NB
Mar 15, 2018

root=Root[1-3 #1+((#1)^3)&,3]; {vals,vals2}=Normal[];
points= Map[Function[x,RootReduce[Sign[x.(root^{0,1,2})](Sqrt[Abs[x.(root^{0,1,2})]])]],vals, {2}];
unitlines=Select[Subsets[points,{2}],Function[x,Chop[N[1-Apply[EuclideanDistance,N[x]]]]==0]];

e=unitlines/.Thread[points->Range[Length[points]]]

g=System`Graph[Range[Length[points]],UndirectedEdge@@@e,VertexCoordinates->points]

RecognizeGraph[g]

UnitDistanceGraphQ[g,WorkingPrecision->∞]//FullSimplify

l={{gn,{0,Append[Most@GraphData[gn,"Embeddings"],ToCommonEdges[g,GraphData[gn]]]}}}

PropertyReplace[l,"Embeddings","11.4"]

RenameGraphFiles[]

Matchstick

GraphData[{"Hamming",{3,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Hamming",{3,3}},"Edges"]]

3D All

GraphData[{"Hamming",{3,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{3,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Hamming",{3,3}},"Polyhedral"]

{"Hamming", {3, 4}}

GraphData[{"Hamming",{3,4}},"StandardName"]

All

GraphData[{"Hamming",{3,4}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,4}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,4}},"LCFSignature"]

GraphData[{"Hamming",{3,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,4}}],Debug->True]//Timing

GraphData[{"Hamming",{3,4}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,4}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{3,4}},{"RCN","CN"}]

GraphData[{"Hamming",{3,4}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,4}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,4}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{3,4}},"Edges"]]

3D All

GraphData[{"Hamming",{3,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{3,4}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {3, 5}}

GraphData[{"Hamming",{3,5}},"StandardName"]

All

GraphData[{"Hamming",{3,5}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,5}},"LCFSignature"]

GraphData[{"Hamming",{3,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,5}}],Debug->True]//Timing

GraphData[{"Hamming",{3,5}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,5}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{3,5}},{"RCN","CN"}]

GraphData[{"Hamming",{3,5}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,5}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cubic",{14,172}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Cubic",{14,172}},"Edges"]]

3D All

GraphData[{"Cubic",{14,172}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cubic",{14,172}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {3, 6}}

GraphData[{"Hamming",{3,6}},"StandardName"]

All

GraphData[{"Hamming",{3,6}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,6}},"LCFSignature"]

GraphData[{"Hamming",{3,6}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,6}}],Debug->True]//Timing

GraphData[{"Hamming",{3,6}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{3,6}},{"RCN","CN"}]

GraphData[{"Hamming",{3,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,6}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,6}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{3,6}},"Edges"]]

3D All

GraphData[{"Hamming",{3,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{3,6}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {3, 7}}

GraphData[{"Hamming",{3,7}},"StandardName"]

All

GraphData[{"Hamming",{3,7}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,7}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,7}},"LCFSignature"]

GraphData[{"Hamming",{3,7}},"LCFNotations"]

GraphData[{"Hamming",{3,7}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,7}}],Debug->True]//Timing

GraphData[{"Hamming",{3,7}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,7}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{3,7}},{"RCN","CN"}]

GraphData[{"Hamming",{3,7}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{3,7}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,7}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{3,7}},"Edges"]]

3D All

GraphData[{"Hamming",{3,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{3,7}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {4, 3}}

GraphData[{"Hamming",{4,3}},"StandardName"]

All

GraphData[{"Hamming",{4,3}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{4,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{4,3}},"LCFSignature"]

GraphData[{"Hamming",{4,3}},"LCFNotations"]

GraphData[{"Hamming",{4,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{4,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{4,3}}],Debug->True]//Timing

GraphData[{"Hamming",{4,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{4,3}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{4,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{4,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{4,3}}],TimeConstraint->300,"Results"->All]//Timing}

g=RotateGraph[,{389,139}]

UnitDistanceGraphEmbeddingQ[g]

Construction as CartesianProduct

g=GraphProduct[CycleGraph[3],GraphData[{"Hamming",{4,3}}]]

RecognizeGraph[g]

Matchstick

GraphData[{"Hamming",{4,3}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{4,3}},{"RCN","CN"}]

GraphData[{"Hamming",{4,3}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{4,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,3}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{4,3}},"Edges"]]

3D All

GraphData[{"Hamming",{4,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{4,3}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {4, 4}}

GraphData[{"Hamming",{4,4}},"StandardName"]

All

GraphData[{"Hamming",{4,4}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{4,4}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{4,4}},"LCFSignature"]

GraphData[{"Hamming",{4,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{4,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{4,4}}],Debug->True]//Timing

GraphData[{"Hamming",{4,4}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{4,4}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{4,4}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{4,4}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{4,4}},{"RCN","CN"}]

GraphData[{"Hamming",{4,4}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{4,4}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,4}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{4,4}},"Edges"]]

3D All

GraphData[{"Hamming",{4,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{4,4}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {4, 5}}

GraphData[{"Hamming",{4,5}},"StandardName"]

All

GraphData[{"Hamming",{4,5}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{4,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{4,5}},"LCFSignature"]

GraphData[{"Hamming",{4,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{4,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{4,5}}],Debug->True]//Timing

GraphData[{"Hamming",{4,5}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{4,5}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{4,5}},{"RCN","CN"}]

GraphData[{"Hamming",{4,5}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{4,5}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,5}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{4,5}},"Edges"]]

3D All

GraphData[{"Hamming",{4,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{4,5}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {4, 6}}

GraphData[{"Hamming",{4,6}},"StandardName"]

All

GraphData[{"Hamming",{4,6}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{4,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{4,6}},"LCFSignature"]

GraphData[{"Hamming",{4,6}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{4,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{4,6}}],Debug->True]//Timing

GraphData[{"Hamming",{4,6}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{4,6}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{4,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{4,6}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{4,6}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{4,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{4,6}},{"RCN","CN"}]

GraphData[{"Hamming",{4,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{4,6}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,6}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

g=Graph[GraphData[{"Hamming",{4,6}},"Edges"]]

3D All

GraphData[{"Hamming",{4,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{4,6}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {5, 3}}

GraphData[{"Hamming",{5,3}},"StandardName"]

All

GraphData[{"Hamming",{5,3}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{5,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{5,3}},"LCFSignature"]

GraphData[{"Hamming",{5,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{5,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{5,3}}],Debug->True]//Timing

GraphData[{"Hamming",{5,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{5,3}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

UnitDistanceGraphEmbeddingQ[]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{5,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{5,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{5,3}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{5,3}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{5,3}},{"RCN","CN"}]

GraphData[{"Hamming",{5,3}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{5,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{5,3}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{5,3}},"Edges"]]

3D All

GraphData[{"Hamming",{5,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{5,3}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {5, 4}}

GraphData[{"Hamming",{5,4}},"StandardName"]

All

GraphData[{"Hamming",{5,4}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{5,4}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{5,4}},"LCFSignature"]

GraphData[{"Hamming",{5,4}},"LCFNotations"]

GraphData[{"Hamming",{5,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{5,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{5,4}}],Debug->True]//Timing

GraphData[{"Hamming",{5,4}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{5,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{5,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{5,4}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{5,4}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{5,4}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{5,4}},{"RCN","CN"}]

GraphData[{"Hamming",{5,4}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{5,4}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{5,4}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{5,4}},"Edges"]]

3D All

GraphData[{"Hamming",{5,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{5,4}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {6, 3}}

GraphData[{"Hamming",{6,3}},"StandardName"]

All

GraphData[{"Hamming",{6,3}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{6,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{6,3}},"LCFSignature"]

GraphData[{"Hamming",{6,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{6,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{6,3}}],Debug->True]//Timing

GraphData[{"Hamming",{6,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{6,3}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

UnitDistanceGraphEmbeddingQ[]

FindUnitDistanceEmbedding[GraphData[{"Hamming",{6,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hamming",{6,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hamming",{6,3}}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{6,3}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hamming",{6,3}},{"RCN","CN"}]

GraphData[{"Hamming",{6,3}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{6,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{6,3}}],"CrossingNumber"->-1]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hamming",{6,3}},"Edges"]]

3D All

GraphData[{"Hamming",{6,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{6,3}},"Graph",{"3D","UnitDistance"}]

Spectra

(2^5)

IntegerSpectrum[HammingGraph[5,2]]//SpectrumForm//TraditionalForm

(2^6)

IntegerSpectrum[HammingGraph[6,2]]//SpectrumForm//TraditionalForm

(2^7)

IntegerSpectrum[HammingGraph[7,2]]//SpectrumForm//TraditionalForm

(2^8)

IntegerSpectrum[HammingGraph[8,2]]//SpectrumForm//TraditionalForm

(3^3)

IntegerSpectrum[HammingGraph[3,3]]//SpectrumForm//TraditionalForm

(3^4)

IntegerSpectrum[HammingGraph[4,3]]//SpectrumForm//TraditionalForm

(3^5)

IntegerSpectrum[HammingGraph[5,3]]//SpectrumForm//TraditionalForm

(3^6)

IntegerSpectrum[HammingGraph[6,3]]//SpectrumForm//TraditionalForm

(3^7)

IntegerSpectrum[HammingGraph[7,3]]//SpectrumForm//TraditionalForm

(4^3)

IntegerSpectrum[HammingGraph[3,4]]//SpectrumForm//TraditionalForm

(4^4)

IntegerSpectrum[HammingGraph[4,4]]//SpectrumForm//TraditionalForm

(4^5)

IntegerSpectrum[HammingGraph[5,4]]//SpectrumForm//TraditionalForm

(4^6)

IntegerSpectrum[HammingGraph[6,4]]//SpectrumForm//TraditionalForm

(5^3)

IntegerSpectrum[HammingGraph[3,5]]//SpectrumForm//TraditionalForm

(5^4)

IntegerSpectrum[HammingGraph[4,5]]//SpectrumForm//TraditionalForm

(5^5)

IntegerSpectrum[HammingGraph[5,5]]//SpectrumForm//TraditionalForm

(6^3)

IntegerSpectrum[HammingGraph[3,6]]//SpectrumForm//TraditionalForm

(6^4)

IntegerSpectrum[HammingGraph[4,6]]//SpectrumForm//TraditionalForm

(7^3)

IntegerSpectrum[HammingGraph[3,7]]//SpectrumForm//TraditionalForm

(7^4)

IntegerSpectrum[HammingGraph[4,7]]//SpectrumForm//TraditionalForm

(8^3)

IntegerSpectrum[HammingGraph[3,8]]//SpectrumForm//TraditionalForm

(8^4)

IntegerSpectrum[HammingGraph[4,8]]//SpectrumForm//TraditionalForm

(9^3)

IntegerSpectrum[HammingGraph[3,9]]//SpectrumForm//TraditionalForm

(10^3)

IntegerSpectrum[HammingGraph[3,10]]//SpectrumForm//TraditionalForm

Minimum Vertex Coloring

HammingGraphSW[d_,q_]:=(verts=Tuples[Range[q],{d}];
dd=Flatten[Table[{i,j,Count[verts[[i]]-verts[[j]],0]==d-1},{i,Length[verts]-1},{j,i+1,Length@verts}],1];
System`Graph[Range[Length[verts]],UndirectedEdge@@@(Most/@Select[dd,#[[-1]]&])])

H(4,5)

g=HammingGraphSW[4,5];

List@@@EdgeList[g]===GraphData[{"Hamming",{4,5}},"EdgeIndices"]

col[i_]:=Mod[Total[verts[[i]]],5,1];
coloring=col/@Range[5^4]

VertexColoringQ[GraphData[{"Hamming",{4,5}}],coloring]

GraphData

GraphDataClassString

GraphDataClassString["Hamming"]

GraphDataString

ham=Sort["Hamming"/.GraphData[#,"NotationRules"]&/@GraphData["Hamming"]]

new=Select[DeleteCases[Complement[Flatten[Table[{d,q},{d,10},{q,2,6}],1],ham],{1,5}],#[[2]]^#[[1]]<1000&]

newer=Select[new,RecognizeGraph[HammingGraph@@#]==={}&]

IsomorphicGraphQ[DistanceRegularGraph["hamming3.7"],HammingGraph[3,7]]

IsomorphicGraphQ[DistanceRegularGraph["hamming4.6"],HammingGraph[4,6]]

file=OpenWrite["~/hamming.m"]

Function[{d,q},WriteString[file,GraphDataString[
HammingGraph[d,q],
"StandardName"->{"Hamming",{d,q}},
"Name"->"("<>ToString[d]<>","<>ToString[q]<>")\[Hyphen]Hamming graph",
"Information"->"HammingGraph",
"Classes"->{"DistanceRegular","Hamming"},
"NotationRules"->{"Hamming"->{d,q}},
"Embeddings"->{},
"Skip"->{"Arboricity","Chord","Chords","ChromaticNumber","CliqueCoveringNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","PathPolynomial","RadioNumber","RadioLabeling","RadioLabelings","RectilinearCrossingCount","Skewness","UnitDistance","Thickness"},
TimeConstraint->10
]]]@@@{{3,7},{5,4},{4,6}};

Close["~/hamming.m"]