Hypercube Graph

Author

Eric W. Weisstein
November 27, 2023

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

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

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

Graceful labeling

(Subscript[Q, 4])

GraphData[{"Hypercube",4},"Graceful"]

lab=GraphData[{"Hypercube",4},"GracefulLabelings"]

lab[[2]]

g=SetProperty[GraphData[{"Hypercube",4}],VertexLabels->Thread[Range[(2^4)]->lab[[2]]]]

GracefullyLabeledGraphQ[g]

Bert Dobbelaere 2020-02-07:

here's a random solution:
 32  0  1 14 10 18 31  3 22 29 27  2  6  9 25 26

<<MathWorld`Graphs`

r=RecognizeGraph@(q4=Nest[GraphCartesianProduct[CompleteGraph[2],#]&,CompleteGraph[2],3])

lab={32,0,1,14,10,18,31,3,22,29,27,2,6,9,25,26};

g=SetProperty[q4,{VertexLabels->Thread[Range[(2^4)]->lab]}]

GracefullyLabeledGraphQ[g]

iso=FindGraphIsomorphism[GraphData[r],q4][[1]]

vorder=Normal[iso][[All,2]]

vlab=lab[[vorder]]

glab=SetProperty[GraphData[r],VertexLabels->Thread[Range[(2^4)]->vlab]]

GracefullyLabeledGraphQ[glab]

(Subscript[Q, 5])

GraphData[{"Hypercube",5},"Graceful"]

lab=GraphData[{"Hypercube",5},"GracefulLabelings"]

lab[[2]]

g=SetProperty[GraphData[{"Hypercube",5}],VertexLabels->Thread[Range[(2^5)]->lab[[2]]]]

GracefullyLabeledGraphQ[g]

Bert Dobbelaere 2020-02-06:

The solution I found for Q_5 is
35,53,76,2,37,7,33,38,77,9,6,67,64,19,55,44,72,0,13,79,40,80,61,46,22,78,60,3,57,18,41,70
Vertex order follows standard binary numbering, nothing fancy.
This one I found by an evolutionary approach. Unfortunately it doesn't scale to larger problem sizes, but I guess if hypercube graphs are known to be graceful, there are probably known constructions to obtain a labeling for any dimension ?

g=SetProperty[GraphData[{"Hypercube",5}],{VertexLabels->Thread[Range[(2^5)]->{35,53,76,2,37,7,33,38,77,9,6,67,64,19,55,44,72,0,13,79,40,80,61,46,22,78,60,3,57,18,41,70}]}]

GracefullyLabeledGraphQ[g]

r=RecognizeGraph@(q5=Nest[GraphCartesianProduct[CompleteGraph[2],#]&,CompleteGraph[2],4])

lab={35,53,76,2,37,7,33,38,77,9,6,67,64,19,55,44,72,0,13,79,40,80,61,46,22,78,60,3,57,18,41,70};

g=SetProperty[q5,{VertexLabels->Thread[Range[(2^5)]->lab]}]

GracefullyLabeledGraphQ[g]

iso=FindGraphIsomorphism[GraphData[r],q5][[1]]

vorder=Normal[iso][[All,2]]

vlab=lab[[vorder]]

glab=SetProperty[GraphData[r],VertexLabels->Thread[Range[(2^5)]->vlab]]

GracefullyLabeledGraphQ[glab]

Counts

A338005

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

Bert Dobbelaere 2020-02-06:
I also counted  466308864 graceful labelings for the 4 dimensional hypercube graph (16V/32E).
For 5 dimensions (32V/80E) it took a long time to just produce one  solution (although there are probably many more). I have no ambition to enumerate them.

Properties

<<MathWorld`Graphs`

Acyclic

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

AdjacencyMatrixCount

A000723

seq=Table[GraphData[{"Hypercube",n},"AdjacencyMatrixCount"],{n,0,6}]

FindSequenceFunction[seq,n+1]

Table[(((2^n)!)/((2^n) n!)),{n,0,6}]

Table[((((2^n)-1)!)/(n!)),{n,6}]

Table[((Gamma[2^n])/(n!)),{n,6}]

FullSimplify[((((2^n)-1)!)/(n!))]

Arboricity

http://dl.acm.org/citation.cfm?id=916846

An investigation of hypercube invariants

Authors:Niall Michael Sylvester GrahamChairs:Frank HararyPublication:· Doctoral DissertationAn investigation of hypercube invariantsNew Mexico State University Las Cruces, NM, USA ©1989

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

Table[Ceiling[(n+1)/2],{n,0,10}]

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

ArcTransitive

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

ArcTransitivity

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

AutomorphismCount

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

FindSequenceFunction[seq,n+1]//FunctionExpand

Table[2^n n!,{n,0,10}]

BalabanIndex

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

seq 2^Range[0,10]

Bandwidth

A036256

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

Sum[Binomial[k,Floor[k/2]],{k,0,n}]

expr=FullSimplify[Sum[Binomial[k,k/2],{k,0,n,2}]+Sum[Binomial[k,(k-1)/2],{k,1,n,2}]]

FullSimplify[expr,Mod[n,2]==0]

FullSimplify[expr,Mod[n,2]==1]

Series[2/((1-z)*(1-2*z+Sqrt[1-4*z^2])),{z,0,10}]

SeriesCoefficient[2/((1-z)*(1-2*z+Sqrt[1-4*z^2])),{z,0,n}]

BridgeCount

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

BurningNumber

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

Possibly 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6

ChordCount

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

Do[Print[{n,Length[Chords[HypercubeGraph[n]]]//Timing}],{n,0,5}]

Table[(2^(n-1)) n,{n,0,5}]

GraphData["Q3","ChordlessCycles"]

GraphData["Q5","CycleCount"]

ChordlessCycleCount

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

ChromaticInvariant

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

GraphData[{"Hypercube",4},"ChromaticPolynomial"][x]//Expand

CoefficientList[%,x]

GraphData[{"Hypercube",5},"ChromaticPolynomial"]

ChromaticNumber

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

Circumference

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

FindSequenceFunction[Drop[seq,2],n-1]

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Hypercube"])

CliqueCount

A132750

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

FindLinearRecurrence[seq]

LinearRecurrence[{5,-8,4},{2,4,9},10]

FindSequenceFunction[seq,n+1]//FullSimplify

CliqueCoveringNumber

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

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

CliqueNumber

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

ComplementOddChordlessCycleCount

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

ConnectedDominatingSetCount

A291704

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationNumber

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

FindSequenceFunction[seq,n]

ConnectedDominationPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Hypercube",n},"ConnectedDominationPolynomial"][x],{n,k0=0,10}],_Missing[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A290758

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

FindSequenceFunction[DeleteCases[seq,_Missing],n+1]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Hypercube",n},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=0,10}],_Missing[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[Piecewise[{{0,n==0}},-1+(((1+x))^n)],{n,k0,kmax}]

FullSimplify[poly2-poly]

CrossingNumber

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

CycleCount

A085408

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

FindSequenceFunction[DeleteCases[seq,0|_Missing],n]

Cyclic

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

CyclomaticNumber

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

FindSequenceFunction[seq,n+1]//FullSimplify

DecagonCount

Not in OEIS as of 2023-04-19

seq=Table[GraphData[{"Hypercube",n},"CyclePolynomial"],{n,0,10}]/.{f_Function:>Coefficient[f[x],x,10],Missing["NotAvailable",l_List]:>FirstCase[l,{10,n_}:>n]}

FindSequenceFunction[seq,n+1]//Factor

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{10,-40,80,-80,32},{0,0,0,6,696},20]

gf=FindGeneratingFunction[seq,x]

ToString[gf,InputForm]

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

seq=CoefficientList[Series[gf,{x,0,20}],x]

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{12,-60,160,-240,192,-64},{0,0,0,0,2112,68736},20]

DetourIndex

A288720

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

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

LinearRecurrence[{14,-56,64},{1,16,184},20]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

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

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

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

Diameter

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

DistinguishingNumber

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

DodecagonCount

Not in OEIS as of 2023-04-19

seq=With[{k=12},Table[GraphData[{"Hypercube",n},"CyclePolynomial"],{n,0,10}]/.{f_Function:>Coefficient[f[x],x,k],Missing["NotAvailable",l_List]:>FirstCase[l,{k,n_}:>n]}]

FindSequenceFunction[seq,n+1]//Factor

coef=FindLinearRecurrence[seq]

gf=FindGeneratingFunction[seq,x,ValidationLength->1]

gf=FindGeneratingFunction[seq,x]

ToString[gf,InputForm]

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

seq=CoefficientList[Series[gf,{x,0,20}],x]

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{12,-60,160,-240,192,-64},{0,0,0,0,2112,68736},20]

DomaticNumber

A157887

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).

seq={1,2,2,4,4,4,5,8,8,8};

DominatingSetCount

A284704

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

FindSequenceFunction[DeleteCases[seq,_Missing],n+1]

rules=Table[k->AdjacencyList[GraphData["Q3"],k],{k,2^3}]

AdjacencyRules[g_System`Graph]:=MapIndexed[#2[[1]]->Sort[Join[#,#2]]&,AdjacencyLists[g]]

AdjacencyRules[GraphData["Q3"]]

Length/@Table[Select[Subsets[Range[2^n]],(CountDistinct[Flatten[#/.Table[k->Prepend[AdjacencyList[HypercubeGraph[n],k],k],{k,2^n}]]]==2^n)&],{n,0,3}]

Table[Count[Subsets[Range[2^n]],_?(CountDistinct[Flatten[#/.Table[k->Prepend[AdjacencyList[HypercubeGraph[n],k],k],{k,2^n}]]]==2^n&)],{n,0,3}]

DominationNumber

A000983

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

DominationPolynomial

(poly=Factor@Table[GraphData[{"Hypercube",n},"DominationPolynomial"],{n,k0=0,kmax=10}]/.f_Function:>f[x])//Column

CoefficientList[Take[poly,4],x]

coef=Factor/@FindLinearRecurrence[DeleteCases[poly,_Missing]]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

EdgeChromaticNumber

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

EdgeConnectivity

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

EdgeCount

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

FindSequenceFunction[seq,n+1]

EdgeCoverCount

A284705

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

FindSequenceFunction[DeleteCases[seq,_Missing],n+1]

FindGeneratingFunction[DeleteCases[seq,_Missing],x]

EdgeCoverNumber

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

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

EulerianCycleCount

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

FaceCount

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

FibonacciCube

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

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

FractionalChromaticNumber

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

FractionalEdgeChromaticNumber

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

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

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

HamiltonianCycleCountQuit

A066037

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

Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n],All]],{n,2,4}],1]

HamiltonianNumber

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

FindSequenceFunction[seq,n+1]

HamiltonianPathCount

A284673

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

VertexCount[HypercubeGraph[n]]

Table[With[{q=HypercubeGraph[n]},Total[Flatten[Table[Length[FindPath[q,i,j,{2^n-1},All]],{j,2^n},{i,j-1}]]]],{n,0,4}]

HamiltonianWalkCount

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

HararyIndex

A290343/A290344

===KirchhoffIndex

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

Transpose[Through[{Numerator,Denominator}[#]]&/@seq]

(seq=Monitor[Table[HararyIndex[HypercubeGraph[n]],{n,13}],n])//Timing

FindSequenceFunction[seq,n]//FullSimplify

Table[-(2^(-1+n)) (HarmonicNumber[n]+(2^(1+n)) Re[LerchPhi[2,1,1+n]]),{n,0,13}]

Expand[-(2^(-1+n)) (HarmonicNumber[n]+(2^(1+n)) Re[LerchPhi[2,1,1+n]])]

Table[-(2^(-1+n)) HarmonicNumber[n]-(4^( n)) Re[LerchPhi[2,1,1+n]],{n,0,13}]

HexagonCount

A290031

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

Table[Length[FindCycle[HypercubeGraph[n],{6},All]],{n,0,9}]//Timing

Table[Length[FindCycle[HypercubeGraph[n],{6},All]],{n,0,10}]//Timing

FindSequenceFunction[seq,n+1]

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

seq=Table[2^(n+1) Binomial[n,3],{n,0,30}]

FindLinearRecurrence[seq]

LinearRecurrence[{8,-24,32,-16},{0,0,0,16},20]

gf=FindGeneratingFunction[seq,x]

ToString[gf,InputForm]

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

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

IndependenceNumber

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

FindSequenceFunction[seq,n+1]

IndependenceRatio

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

FindSequenceFunction[seq,n]

IndependentEdgeSetCount

A045310

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

IndependentVertexSetCount

A027624

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

Do[Print[{n,Length[FindAllIndependentVertexSets[GraphData[{"Hypercube",n}]]]//Timing,MaxMemoryUsed[]/10^9.GB}],{n,7}]

Table[Length[Union@@(Subsets/@FindIndependentVertexSet[HypercubeGraph[n],Infinity,All])],{n,0,5}]

IrredundantSetCount

A290512

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

(seq=Table[Length[IrredundantSets[HypercubeGraph[n]]],{n,0,4}])//Timing

IntersectionNumber

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

KirchhoffIndex

A290343/A290344

===HararyIndex

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

Do[Print[{n,KirchhoffIndex[HypercubeGraph[n]]//Timing}],{n,12}]

seq={0,1,5,(58/3),(206/3),(3548/15),(12136/15),(291824/105),(1012048/105),(10650848/315),(7560128/63),298378880/693,1081081600/693,51358504448/9009};

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

seq=Table[-(2^(n-1)) HarmonicNumber[n]-(4^n) Re[LerchPhi[2,1,n+1]],{n,0,40}]

FindLinearRecurrence[seq]

Numerator[seq]

Denominator[seq]

KirchhoffSumIndex

A290346/A290345

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

seq={0,1,4,(227/18),(334/9),(96661/900),(140663/450),(10194871/11025),(30803116/11025),(6854577137/793800),(10830776629/396900),4228148644729/48024900,3474650044156/12006225,7849737483616471/8116208100};

Numerator[seq]

Denominator[seq]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

LeafCount

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

LongestCycleCount

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

LovaszNumber

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

LucasCube

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

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

MatchingNumber

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

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

MatchingPolynomial

Table[Binomial[n,k]2^(n-k),{k,0,4}]

Table[Expand[(2x+1)^n],{n,6}]//TableForm

MaximalCliqueCount

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

FindSequenceFunction[seq,n+1]

FindSequenceFunction[Rest@seq,n]

MaximalIndependentEdgeSetCount

A284706

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

MaximalIndependentVertexSetCount

A284707

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

FindSequenceFunction[DeleteCases[seq,_Missing],n+1]

FindGeneratingFunction[DeleteCases[seq,_Missing],x]

MaximumCliqueCount

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

FindSequenceFunction[seq,n+1]

FindSequenceFunction[Rest@seq,n]

MaximumIndependentEdgeSetCount

A005271

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

MaximumIndependentVertexSetCount

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

MaximumLeafNumber

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

MaximumVertexDegree

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

MeanDistance

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

FindSequenceFunction[seq,n+1]

MinimalDominatingSetCount

A290406

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

MinimalDominatingSetSignature

seq=Table[GraphData[{"Hypercube",n},"MinimalDominatingSetSignature"],{n,0,10}]//Column

MinimumCliqueCoveringCount

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

MinimumConnectedDominatingSetCount

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

MinimumDistinguishingLabelingCount

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

MinimumDominatingSetCount

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

MinimumEdgeCoverCount

A005271

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

MinimumVertexDegree

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

MolecularTopologicalIndex

A192831

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

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n+1]

FindGeneratingFunction[seq,x]

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

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

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

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

FindLinearRecurrence[seq]

LinearRecurrence[{18,-132,504,-1056,1152,-512},{4,48,360,2304,13600,76032},{0,30}]

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]//Simplify

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

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

Nonhamiltonian

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

OctagonCount

A364688

seq=Table[GraphData[{"Hypercube",n},"CyclePolynomial"],{n,0,10}]/.{f_Function:>Coefficient[f[x],x,8],Missing["NotAvailable",l_List]:>FirstCase[l,{8,n_}:>n]}

Table[Length[FindCycle[HypercubeGraph[n],{8},All]],{n,0,8}]//Timing

Table[Length[FindCycle[HypercubeGraph[n],{8},All]],{n,0,9}]//Timing

FindSequenceFunction[seq,n+1]//Factor

n=.

Binomial[n,3]

seq=Table[(2^(n-4)) n(n-1)(n-2) (27n-79),{n,0,25}]

ToString[seq]//StringLength

Table[3 (2^(n-3)) Binomial[n,3] (27n-79),{n,0,10}]

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{10,-40,80,-80,32},{0,0,0,6,696},20]

gf=FindGeneratingFunction[seq,x]

ToString[gf,InputForm]

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

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

OddChordlessCycleCount

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

PathCount

A291996

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

PathPolynomial

(poly=Factor[Table[GraphData[{"Hypercube",n},"PathPolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

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

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Pell

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

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

PentagonCount

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

Perfect

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

ProjectivePlaneCrossingNumber

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

Radius

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

RectilinearCrossingNumber

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

Skewness

A291526

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

FindSequenceFunction[Drop[seq,3],n-2]//FullSimplify

Table[Piecewise[{{0,n==0||n==1}},(2^(n-1)) (n-4)+4],{n,0,10}]

Do[Print[{i,GraphSkewness[GraphData[{"Hypercube",i}]]//Timing}],{i,5}]

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

seq=Table[(2^n)(n-3)+4,{n,40}]

FindLinearRecurrence[seq]

LinearRecurrence[{5,-8,4},{0,0,4},20]

gf=x FindGeneratingFunction[seq,x]

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

SpanningTreeCount

A006237

seq=Table[GraphData[{"Hypercube",n},"SpanningTreeCount"],{n,0,5}]

FindSequenceFunction[Rest@seq,n]

gf=FindGeneratingFunction[seq,x]

Table[2^(2^n-1-n)Product[k^Binomial[n,k],{k,n}],{n,0,5}]

Product[k^Binomial[n,k],{k,n}]

SquareCount

A001788

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

FindSequenceFunction[seq,n+1]

2^(n-2)Binomial[n,2]

StabilityIndex

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

FindSequenceFunction[seq,n+1]

FindGeneratingFunction[seq,x]

TopologicalIndex

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

FindSequenceFunction[seq,n+1]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

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

Traceable

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

TriangleCount

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

Untraceable

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

VertexConnectivity

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

VertexCount

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

FindSequenceFunction[seq,n+1]

VertexCoverNumber

Related to but not the same as IndependenceNumber

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

FindSequenceFunction[seq,n+1]

gf=FindGeneratingFunction[seq,x]

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

VertexDegrees

seq=Table[GraphData[{"Hypercube",n},"VertexDegrees"],{n,5}]

VertexTransitive

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

WienerIndex

A002697

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

FindSequenceFunction[seq,n+1]

FindLinearRecurrence[seq]

gf=FindGeneratingFunction[seq,x]

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

WienerSumIndex

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

FindSequenceFunction[seq,n+1]

Embeddings

{"Hypercube", n}

Combinatorica

ShowGraphArray[Table[Hypercube[i],{i,5}],VertexStyle->Disk[.07],VertexColor->Red]

HypercubeGraph

GraphicsRow[Table[HypercubeGraph[n],{n,2,6}]]//StyleGraphs

GraphData

GraphicsRow[Table[Show[StyleGraphs[GraphData[{"Hypercube",n}],VertexSize->{"Scaled",If[n<5,.06,.04]}],LabelStyle->Directive[Black,FontFamily->"Times"],PlotLabel->Subscript[Style["Q",Italic],n]],{n,2,6}],ImageSize->400,Spacings->-5]

Isometric

GraphicsRow[Table[Show[StyleGraphs[HypercubeGraphIsometric[n],VertexSize->{"Scaled",If[n<5,.06,.04]}],PlotLabel->Subscript[Style["Q",Italic],n],LabelStyle->Directive[Black,FontFamily->"Times"]],{n,2,6}],ImageSize->400,Spacings->-5]

{"Hypercube", 4}

Default

GraphData[{"Hypercube",4},"Graph"]//StyleGraphs

All

GraphData[{"Hypercube",4},"AllImages"]

Isometric

Show[g=HypercubeGraphIsometric[4]//StyleGraphs]

RecognizeGraph[g]

Rotation

Table[With[{n=VertexCount[g1],e=EdgeList[g1],v=GraphEmbedding[g1]},Graph[Range[2n],Join[e,e/.i_Integer:>i+n,Table[UndirectedEdge[i,i+n],{i,n}]],VertexCoordinates->Join[v,{Cos[q],Sin[q]}+#&/@v]]],{q,0Degree,90Degree,5Degree}]

{"Hypercube", 5}

Default

GraphData[{"Hypercube",5},"Graph"]//StyleGraphs

All

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

LCF

GraphData[{"Hypercube",5},"HamiltonianCycleCount"]

GraphData[{"Hypercube",5},"LCFNotations"]

Tally[%[[2,All,-1]]]

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

Isometric

g=HypercubeGraphIsometric[5]//StyleGraphs

RecognizeGraph[g]

With[{n=5},HypercubeGraphIsometric[n,#]&/@Subsets[Range[n],{2}]]

Rotation

Table[With[{n=VertexCount[g1],e=EdgeList[g1],v=GraphEmbedding[g1]},Graph[Range[2n],Join[e,e/.i_Integer:>i+n,Table[UndirectedEdge[i,i+n],{i,n}]],VertexCoordinates->Join[v,{Cos[q],Sin[q]}+#&/@v]]],{q,0Degree,90Degree,5Degree}]

{"Hypercube", 6}

GraphData[{"Hypercube",6},"StandardName"]

Default

GraphData[{"Hypercube",6}]//StyleGraphs

All

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

Halin

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

LCF

GraphData[{"Hypercube",6},"HamiltonianCycleCount"]

GraphData[{"Hypercube",6},"LCFNotations"]

GraphData[{"Hypercube",6},"LCFSignature"]

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

Isometric

g=HypercubeGraphIsometric[6]//StyleGraphs

RecognizeGraph[g]

With[{n=6},GraphicsGrid[Partition[StyleGraphs[HypercubeGraphIsometric[n,#]]&/@Subsets[Range[n],{2}],UpTo[6]]]]

UnitDistance

GraphData[{"Hypercube",6},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Hypercube",6},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Hypercube",6}],TimeConstraint->500,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Hypercube",6},{"RCN","CN"}]

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hypercube",6}]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hypercube",6},"Edges"]]

3D All

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

{"Hypercube", 7}

Default

GraphData[{"Hypercube",7}]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

All

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

LCF

GraphData[{"Hypercube",7},"HamiltonianCycleCount"]

GraphData[{"Hypercube",7},"LCFNotations"]

%[[2,All,-1]]//Tally

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

Isometric

g=HypercubeGraphIsometric[7]//StyleGraphs

RecognizeGraph[g]

With[{n=7},GraphicsGrid[Partition[StyleGraphs[HypercubeGraphIsometric[n,#]]&/@Subsets[Range[n],{2}],UpTo[6]]]]

UnitDistance

GraphData[{"Hypercube",7},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

MinimalCrossing

GraphData["Foster128B",{"RCN","CN"}]

GraphData["Foster128B","Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData["Foster128B","Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["Foster128B"],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Hypercube", 8}

Default

GraphData[{"Hypercube",8}]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

All

GraphData[{"Hypercube",8},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Hypercube",8},"HamiltonianCycleCount"]

GraphData[{"Hypercube",8},"LCFNotations"]

%[[2,All,-1]]//Tally

GraphData[{"Hypercube",8},"Graph","LCF"]//StyleGraphs

Isometric

g=HypercubeGraphIsometric[8]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

RecognizeGraph[g]

With[{n=8},GraphicsGrid[Partition[StyleGraphs[Union[HypercubeGraphIsometric[n,#]&/@Subsets[Range[n],{2}]]],UpTo[6]],ImageSize->1000]]

UnitDistance

GraphData[{"Hypercube",8},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hypercube",8}],Debug->True]//Timing

GraphData[{"Hypercube",8},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

MinimalCrossing

GraphData[{"Hypercube",8},{"RCN","CN"}]

GraphData[{"Hypercube",8},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hypercube",8},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hypercube",8}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hypercube",8},"Edges"]]

3D All

GraphData[{"Hypercube",8},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hypercube",8},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Hypercube",8},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"Hypercube",8},"Polyhedron"]}]

{"Hypercube", 9}

Default

GraphData[{"Hypercube",9}]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

All

GraphData[{"Hypercube",9},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Hypercube",9},"HamiltonianCycleCount"]

GraphData[{"Hypercube",9},"LCFNotations"]

%[[2,All,-1]]//Tally

Show[#,ImageSize->Medium]&/@GraphData[{"Hypercube",9},"Graph","LCF"]

Isometric

g=HypercubeGraphIsometric[9]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

RecognizeGraph[g]

With[{n=9},GraphicsGrid[Partition[StyleGraphs[HypercubeGraphIsometric[n,#]]&/@Subsets[Range[n],{2}],UpTo[6]]]]

UnitDistance

GraphData[{"Hypercube",9},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hypercube",9}],Debug->True]//Timing

GraphData[{"Hypercube",9},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hypercube",9},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hypercube",9},{"RCN","CN"}]

GraphData[{"Hypercube",9},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hypercube",9},"Edges"]

g=UnitDistanceEmbeddingRefine@Graph[GraphData[{"Hypercube",9},"Edges"]]

UnitDistanceGraphEmbeddingQ@g

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hypercube",9}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

g=Graph3D[GraphData[{"Hypercube",9},"Edges"]]

3D All

GraphData[{"Hypercube",9},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hypercube",9},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Hypercube",9},"Graph",{"3D","Polyhedron"}]

{"Hypercube", 10}

Default

GraphData[{"Hypercube",10}]//StyleGraphs

All

GraphData[{"Hypercube",10},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Hypercube",10},"HamiltonianCycleCount"]

GraphData[{"Hypercube",10},"LCFNotations"]

%[[2,All,-1]]//Tally

Show[#,ImageSize->Medium]&/@GraphData[{"Hypercube",10},"Graph","LCF"]

Isometric

g=HypercubeGraphIsometric[10]//StyleGraphs

RecognizeGraph[g]

With[{n=10},GraphicsGrid[Partition[StyleGraphs[HypercubeGraphIsometric[n,#]]&/@Subsets[Range[n],{2}],UpTo[6]],ImageSize->1000]]

UnitDistance

GraphData[{"Hypercube",10},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hypercube",10}],Debug->True]//Timing

GraphData[{"Hypercube",10},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hypercube",10},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Hypercube",10},{"RCN","CN"}]

GraphData[{"Hypercube",10},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hypercube",10},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hypercube",10}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Hypercube",10},"Edges"]]

3D All

GraphData[{"Hypercube",10},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hypercube",10},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Hypercube",10},"Graph",{"3D","Polyhedron"}]

Construction

Graph Cartesian Product

RecognizeGraph/@NestList[GraphCartesianProduct[CompleteGraph[2],#]&,CompleteGraph[2],5]

Hamming Distance

HypercubeGraph1[n_Integer]:=Module[
{
v=Tuples[{-1,1},n],
s=Subsets[Range[2^n],{2}],
e
},
e=Pick[s,HammingDistance@@v[[#]]&/@s,1];
System`Graph[Range[2^n],UndirectedEdge@@@e]
]

Table[Print[{n,HypercubeGraph1[n];//Timing}],{n,10}];

RecognizeGraph/@Table[HypercubeGraph1[n],{n,10}]

Cayley Graph

RecognizeGraph/@Table[UndirectedGraph[CayleyGraph[AbelianGroup[Table[2,{n}]]]],{n,10}]

Unit-distance embeddings

Embeddings

gs={#1,#2[[1]]}&@@@DeleteCases[{#,GraphData[#,"Graph","UnitDistance"]}&/@SortBy[GraphData["Hypercube"],GraphData[#,"V"]&],{_,{}}];

GraphicsGrid[Partition[Show[StyleGraphs[#2,VertexSize->Switch[#,
"SingletonGraph",.02,
{"Path",2},.07,
_,{"Scaled",.06}]],
PlotLabel->TextCell[GraphData[#1,"Name"],PageWidth->100,TextAlignment->Center],LabelStyle->Directive[Black,FontFamily->"Times",Italic]]&@@@gs,UpTo[5]],Alignment->Top,ImageSize->700,Dividers->All]

GraphData

GraphDataClassString

GraphDataClassString["Hypercube"]