Cube-Connected Cycle Graph

Author

Eric W. Weisstein
August 2, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Cube-ConnectedCycleGraph.nb.

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

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

Embeddings

Combinatorica (wrong for n > 4)

<<Combinatorica`

ShowGraphArray[Table[CubeConnectedCycle[d],{d,4}]]

GraphicsRow[GraphPlot[Rule@@@Edges[#]]&/@Table[CubeConnectedCycle[n],{n,3}]]

ToEntity/@(System`Graph[UndirectedEdge@@@Edges[#]]&/@Table[CubeConnectedCycle[n],{n,3,5}])

CombinatoricaGraphToV8Graph[g_Combinatorica`Graph,opts___?OptionQ]:=Quiet[Check[AdjacencyGraph[ToAdjacencyMatrix[g],opts,DirectedEdges->!UndirectedQ[g],VertexCoordinates->Combinatorica`Vertices[g]],$Failed]]

CombinatoricaCubeConnectedCycleGraph[n_]:=CombinatoricaGraphToV8Graph[CubeConnectedCycle[n]]

RecognizeGraph/@Table[CombinatoricaCubeConnectedCycleGraph[n],{n,3,8}]

CombinatoricaCubeConnectedCycleGraph[4]

IsomorphicGraphQ[CombinatoricaCubeConnectedCycleGraph[4],haythorpe]

Through[{VertexCount,EdgeCount,GraphDiameter}[CombinatoricaCubeConnectedCycleGraph[4]]]

GraphData V7 (uses Combinatorica's wrong definition)

Wrong for n>3

GraphPlot[Graph[#],Method->None]&/@SortBy[GraphData["CubeConnectedCycle"],GraphData[#,"V"]&]

GraphData

SortBy[GraphData["CubeConnectedCycle"],GraphData[#,"V"]&]

Table[GraphData[{"CubeConnectedCycle",n}],{n,3,5}]//StyleGraphs

ToEntity/@Table[GraphData[{"CubeConnectedCycle",n}],{n,3,5}]

Sykora and Vrt'o 1993 ((Subscript[CCC, 3]))

v=Flatten[Table[{x,y},{x,0,7},{y,0,2}],1]

g=Graph[Range[Length[v]],UndirectedEdge@@@Join[
Flatten[Table[{{i,i+1},{i+1,i+2}},{i,1,22,3}],1],
Table[{i,i+2},{i,1,22,3}],
{{1,4},{7,10},{13,16},{19,22},{3,15},{6,18},{9,21},{12,24},{2,8},{5,11},{14,20},{17,23}}],VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

Clancy et al. 1989 ((Subscript[CCC, 4])) [wrong?]

https://arxiv.org/pdf/1901.05155.pdf

Graphics[Point[v0={{300.34765625`,100.87890625`},{421.94921875`,149.8203125`},{179.234375`,150.67578125`},{301.98046875`,182.9140625`},{363.3828125`,207.4140625`},{237.69140625`,207.71484375`},{470.20703125`,270.55078125`},{389.56640625`,271.33984375`},{212.48828125`,270.5234375`},{130.4609375`,270.71484375`},{363.98046875`,333.41015625`},{237.296875`,333.57421875`},{300.1953125`,359.8984375`},{421.3359375`,392.12109375`},{180.55859375`,392.61328125`},{300.48046875`,441.47265625`}}]]

v=Round[v0]

v4=Flatten[Function[vv,vv+8#&/@{{-1,-1},{-1,1},{1,1},{1,-1}}]/@v,1]

m=MinMax/@Transpose[v4]

Subtract@@@vv

vv=(#-{122,93})&/@v4

vv={{170,0},{170,16},{186,16},{186,0},{292,49},{292,65},{308,65},{308,49},{49,50},{49,66},{65,66},{65,50},{172,82},{172,98},{188,98},{188,82},{233,106},{233,122},{249,122},{249,106},{108,107},{108,123},{124,123},{124,107},{340,170},{340,186},{356,186},{356,170},{260,170},{260,186},{276,186},{276,170},{82,170},{82,186},{98,186},{98,170},{0,170},{0,186},{16,186},{16,170},{234,232},{234,248},{250,248},{250,232},{107,233},{107,249},{123,249},{123,233},{170,259},{170,275},{186,275},{186,259},{291,291},{291,307},{307,307},{307,291},{51,292},{51,308},{67,308},{67,292},{170,340},{170,356},{186,356},{186,340}};

Length[v4]

e0=Sort[Sort/@Flatten[Partition[#,2,1,1]&/@Partition[Range[64],4],1]]

vv/356.

g=System`Graph[Range[Length[vv]],UndirectedEdge@@@(Sort/@Sort[Join[e0,{{4,8},{7,28},{27,56},{55,63},{59,62},{38,58},{10,37},{1,9},{5,16},{12,13},{11,33},{34,57},{47,61},{43,64},{26,44},{50,60},{51,54},{19,25},{31,53},{6,32},{15,41},{14,45},{30,48},{35,42},{23,49},{18,52},{2,21},{3,20},{17,36},{24,29},{39,46},{22,40}}]]),VertexCoordinates->vv/356.,VertexLabels->"Name"]

haythorpe=;

With[{n=4},2n+Floor[n/2]-2]

Through[{VertexCount,EdgeCount,GraphDiameter}[CubeConnectedCycleGraph[4]]]

Through[{VertexCount,EdgeCount,GraphDiameter}[haythorpe]]

CubicGraphQ[haythorpe]

IsomorphicGraphQ[haythorpe,CubeConnectedCycleGraph[4]]

Special Cases

TextGrid[{"CubeConnectedCycle"/.GraphData[#,"NotationRules"],GraphData[#,"Name"]}&/@DeleteCases[GraphData["CubeConnectedCycle"],{"CubeConnectedCycle",_}],Dividers->All]

n==3

GraphData[{"CubeConnectedCycle",3},"Graph","All"]/.g_System`Graph:>SetProperty[g,{VertexSize->{"Scaled",.02},System`VertexStyle->Red,System`EdgeStyle->Black}]

n==4

GraphData[{"CubeConnectedCycle",4},"Graph","All"]/.g_System`Graph:>SetProperty[g,{VertexSize->{"Scaled",.025},System`VertexStyle->Red,System`EdgeStyle->Gray,ImageSize->100}]

Properties

Acyclic

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

AdjacencyMatrixCount

seq=Table[GraphData[{"CubeConnectedCycle",n},"AdjacencyMatrixCount"],{n,3,5}]

FindSequenceFunction[seq,n-2]//FullSimplify

Table[((((2^n) n)!)/((2^(1+n)) n)),{n,3,5}]

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

Arboricity

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

ArcTransitive

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

ArcTransitivity

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

AutomorphismCount

seq=DeleteCases[GraphData[{"CubeConnectedCycle",#},"|Aut|"]&/@Range[3,8],_Missing]

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

FullSimplify[SeriesCoefficient[x^3FindGeneratingFunction[seq,x],{x,0,n}],n>2]

BalabanIndex

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

FindSequenceFunction[%,n-2]

Bandwidth

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

BridgeCount

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

BurningNumber

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

CharacteristicPolynomial

(poly=Factor@Table[GraphData[{"CubeConnectedCycle",n},"CharacteristicPolynomial"][x],{n,k0=3,8}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ChordCount

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

ChordlessCycleCount

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

ChromaticInvariant

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

ChromaticNumber

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

FindSequenceFunction[seq,n-2]//FullSimplify

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

Circumference

A036289

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

FindSequenceFunction[seq,n-2]

CliqueCount

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

FindSequenceFunction[seq,n-2]

Classes

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

ComplementOddChordlessCycleCount

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

ConnectedDominatingSetCount

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationNumber

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Complete",n},"ConnectedDominationPolynomial"][x],{n,k0=2,6}],_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

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

FindSequenceFunction[DeleteCases[seq,_Missing],n-2]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Complete",n},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=2,6}],_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]

CycleCount

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

Cyclic

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

CyclomaticNumber

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

FindSequenceFunction[seq,n-2]//FullSimplify

DetourIndex

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

FindSequenceFunction[DeleteCases[seq,_Missing],n-2]

Diameter

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

Wikipedia says 2 n + ⌊n/2⌋ − 2

Table[2n+Floor[n/2]-2,{n,3,8}]

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

Do[Print[{{"CubeConnectedCycle",n},GraphDiameter[CubeConnectedCycleGraph[n]]//Timing}],{n,3,12}]

Table[Piecewise[{{6, n == 3}}, -2 + 2*n + Floor[n/2]],{n,3,12}]

FindSequenceFunction[seq,n-2]

FindSequenceFunction[Rest@seq,n-3]

DomaticNumber

Possibly 4

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

DominatingSetCount

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

DominationNumber

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

FindSequenceFunction[seq,n-2]

EdgeChromaticNumber

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

EdgeConnectivity

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

EdgeCount

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

FindSequenceFunction[seq,n-2]

Table[n 2^n,{n,3,8}]

EulerianCycleCount

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

FaceCount

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

FibonacciCube

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

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

FractionalChromaticNumber

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

Table[Piecewise[{{2,Mod[n,2]==0},{((2n)/(n-1)),Mod[n,2]==1}}],{n,3,8}]

%==seq

Girth

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

FindSequenceFunction[seq,n-2]

HamiltonDecompositionCount

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

Hamiltonian

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

HamiltonianCycleCount

DeleteCases[GraphData[{"CubeConnectedCycle",#},"HamiltonianCycleCount"]&/@Range[3,8],_Missing]

HamiltonianPathCount

DeleteCases[GraphData[{"CubeConnectedCycle",#},"HamiltonianPathCount"]&/@Range[3,8],_Missing]

HamiltonianWalkCount

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

HararyIndex

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

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n-2]

HexagonCount

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

Do[Print[GraphCycleCount[CubeConnectedCycleGraph[n],6]//Timing],{n,3,15}]

HosoyaIndex

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

IndependenceNumber

A291938

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

FindSequenceFunction[seq,n-2]//FullSimplify

FindSequenceFunction[Rest@seq,n-3]//FullSimplify

Table[(2^(n-1)) n Piecewise[{{1,Mod[n,2]==0},{((n-1)/n),Mod[n,2]==1}}],{n,3,8}]

FullSimplify[(2^n) n Piecewise[{{1/2,Mod[n,2]==0},{((n-1)/(2n)),Mod[n,2]==1}}]]

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

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

IndependenceRatio

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

FindSequenceFunction[seq,n-2]

Table[Piecewise[{{1/2,Mod[n,2]==0},{((n-1)/(2n)),Mod[n,2]==1}}],{n,3,8}]

IndependentEdgeSetCount

A293127

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

IndependentVertexSetCount

A292701

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

KirchhoffIndex

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

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

KirchhoffSumIndex

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

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

LeafCount

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

LongestCycleCount

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

Same as HamiltonianCycleCount

LucasCube

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

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

MaximalCliqueCount

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

FindSequenceFunction[Rest@seq,n-2]

Do[Print[{n,Length[FindClique[CubeConnectedCycleGraph[n],Infinity,All]]//Timing}],{n,3,12}]

gf=(x^3)FindGeneratingFunction[{20,96,240,576,1344,3072,6912,15360,33792,73728},x]

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

Table[Piecewise[{{20,n==3}},3 (2^(-1+n)) n],{n,3,12}]

MaximalIndependentEdgeSetCount

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

MaximalIndependentVertexSetCount

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

MaximumCliqueCount

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

FindSequenceFunction[Rest@seq,n-3]

Do[Print[{n,Length[FindClique[CubeConnectedCycleGraph[n],Length/@FindClique[CubeConnectedCycleGraph[n]],All]]//Timing}],{n,3,12}]

Table[Piecewise[{{8,n==3}},3 (2^(-1+n)) n],{n,3,12}]

MaximumIndependentEdgeSetCount

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

MaximumIndependentVertexSetCount

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

MaximumVertexDegree

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

MeanDistance

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

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

seq={};
Do[Print[{n,(AppendTo[seq,s=Mean[Flatten[GraphDistanceMatrix[CubeConnectedCycleGraph[n]]]]];s)//Timing}],{n,3,11}]

FindSequenceFunction[seq,n-2]

MinimalDominatingSetCount

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

MinimalDominatingSetSignature

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

MinimumCliqueCoveringCount

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

MinimumConnectedDominatingSetCount

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

MinimumDistinguishingLabelingCount

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

MinimumDominatingSetCount

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

MinimumEdgeCoverCount

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

MinimumVertexCoverCount

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

MinimumVertexDegree

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

MolecularTopologicalIndex

A192191

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

FindSequenceFunction[seq,n-2]//FullSimplify

FindGeneratingFunction[seq,x]

Nonhamiltonian

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

OddChordlessCycleCount

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

Pell

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

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

PentagonCount

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

Do[Print[GraphCycleCount[CubeConnectedCycleGraph[n],5]//Timing],{n,3,15}]

Radius

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

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

Do[Print[{{"CubeConnectedCycle",n},GraphRadius[CubeConnectedCycleGraph[n]]//Timing}],{n,3,9}]

FindSequenceFunction[seq,n-2]//FullSimplify

Table[Piecewise[{{6,n==3}},2n+Floor[n/2]-2],{n,3,11}]

SpanningTreeCount

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

FindSequenceFunction[seq,n-2]//FullSimplify

FindGeneratingFunction[seq,x]

SquareCount

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

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

Do[Print[GraphCycleCount[CubeConnectedCycleGraph[n],4]//Timing],{n,3,15}]

StabilityIndex

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

FindSequenceFunction[seq,n-2]

FindGeneratingFunction[seq,x]

TopologicalIndex

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

Traceable

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

TriangleCount

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

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

Do[Print[GraphCycleCount[CubeConnectedCycleGraph[n],3]//Timing],{n,3,15}]

Untraceable

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

VertexConnectivity

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

VertexCount

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

FindSequenceFunction[seq,n-2]

Table[n 2^n,{n,3,8}]

VertexCoverCount

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

VertexDegrees

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

WienerIndex

A292028

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

Do[Print[{{"CubeConnectedCycle",n},WienerIndex[CubeConnectedCycleGraph[n]]//Timing}],{n,3,10}]

seq={1,64,888,9472,76160,556032,3605504,22224896,128471040,719708160,3874455552,20416954368,104732426240,528985096192,2620635217920,12831147687936,61916622880768,296036213981184,1399459946692608,6566769862901760};

FindSequenceFunction[seq,n]

FindLinearRecurrence[Drop[seq,3]]

gf=x FindGeneratingFunction[seq,x]

WienerSumIndex

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

FindSequenceFunction[seq,n-2]

Construction

Combinatorica

Inefficient but literally follows the definition
John Novak, 2/27/2011

cccg[m_] :=
 Module[{hg = Hypercube[m], hcv, hcl, cycles, paired, cycleedges},
  hcv = V[hg];
  hcl = ToAdjacencyLists[hg];
(* create a list of new vertices, grouped by the cycles for each vertex *)
  cycles = Table[(n - 1) * m  + k, {n, 1, hcv}, {k, 1, m }];
(* create the edges that correspond to the edges of the hypercube, mapped
   from the new vertices - the Union/Sort is because the internal part
   ends up creating the directed edges (one each way), and I want the
   undirected edges -- there's probably a better way, but as I said, this
   is a dirty implementation *)
  paired = 
   Union[Sort /@ 
     Flatten[MapIndexed[{cycles[[##]] & @@ #2, 
         cycles[[#1, 
           First[First[Position[hcl[[#1]], First[#2]]] ]]]} &, 
       hcl, {2}], 1]];
(* create the edges of the cycles *)
  cycleedges = 
   Flatten[Transpose[{cycles, RotateLeft /@ cycles}, {3, 2, 1}], 1];
(* join them up and output the graph *)
 FromUnorderedPairs[Join[paired, cycleedges]]
 ]

ToEntity/@(System`Graph[UndirectedEdge@@@Edges[#]]&/@Table[CubeConnectedCycle[n],{n,3,5}])

M/@Table[CubeConnectedCycle[n],{n,3,8}]

GraphDiameter/@(System`Graph[UndirectedEdge@@@Edges[#]]&/@Table[CubeConnectedCycle[n],{n,3,8}])

Note GraphDiameter disagrees with value given by wikipedia, so whatever the above is, it is not the cube-connected cycle graph (though it has the same number of edges and vertices).

Wikipedia

https://en.wikipedia.org/wiki/Cube-connected_cycles

The cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle.

The cube-connected cycles of order n (denoted CCCn) can be defined as a graph formed from a set of n2n nodes, indexed by pairs of numbers (x, y) where 0 ≤ x < 2n and 0 ≤ y < n. Each such node is connected to three neighbors: (x, (y + 1) mod n), (x, (y − 1) mod n), and (x ⊕ 2y, y), where "⊕" denotes the bitwise exclusive or operation on binary numbers.

Table[CubeConnectedCycleGraph[n],{n,3,7}];//Timing

ToEntity/@Table[CubeConnectedCycleGraph[n],{n,3,8}]

EdgeCount/@Table[CubeConnectedCycleGraph[n],{n,3,8}]

GraphDiameter/@Table[CubeConnectedCycleGraph[n],{n,3,8}]

Table[2n+Floor[n/2]-2,{n,3,8}]

Embeddings

<<MathWorld`Graphs`

{"CubeConnectedCycle", 3} == "TruncatedCubicalGraph"

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

{"CubeConnectedCycle", 4}

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

GraphData[{"CubeConnectedCycle",4},"StandardNames"]

GraphData[{"CubeConnectedCycle",4},"NotationRules"]

GraphData[{"CubeConnectedCycle",4},"Notation"]

Primary

GraphData[{"CubeConnectedCycle",4}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubeConnectedCycle",4},"EdgeList"]]

Default embedding

g=Graph[GraphData[{"CubeConnectedCycle",4},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubeConnectedCycle",4},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubeConnectedCycle",4},"Graph","Degenerate"]

Bilateral

GraphData[{"CubeConnectedCycle",4},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubeConnectedCycle",4},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubeConnectedCycle",4},"Planar"]

GraphData[{"CubeConnectedCycle",4},"Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubeConnectedCycle",4},"Circulant"]

GraphData[{"CubeConnectedCycle",4},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubeConnectedCycle",4},"Halin"]

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

Rigid

GraphData[{"CubeConnectedCycle",4},"Rigid"]

GraphData[{"CubeConnectedCycle",4},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubeConnectedCycle",4},"Flexible"]

GraphData[{"CubeConnectedCycle",4},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubeConnectedCycle",4},"LCF"]

GraphData[{"CubeConnectedCycle",4},"HamiltonianCycleCount"]

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

GraphData[{"CubeConnectedCycle",4},"LCFNotations"]

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

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubeConnectedCycle",4}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

(gs=
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Flatten[Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],1])//Timing

Length[gs]

UnitDistance

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

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

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

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

UnitDistanceEmbeddingRefine

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

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

UnitDistance subgraph construction

GraphData[#,"V"]&/@{{"TorusGrid",{8,8}},{"CubeConnectedCycle",4}}

iso=FindSubgraphIsomorphism[GraphData[{"CubeConnectedCycle",4}],GraphData[{"TorusGrid",{8,8}}]][[1]]

With[{g=GraphData[{"CubeConnectedCycle",4}]},Graph[Range[64],EdgeList[g]/.iso,VertexCoordinates->GraphData[{"TorusGrid",{8,8}},"Embeddings","UnitDistance"][[1]]]]

RecognizeGraph[%]

gs=With[{g=GraphData[{"CubeConnectedCycle",4}]},Graph[Range[64],EdgeList[g]/.iso,VertexCoordinates->#]]&/@GraphData[{"TorusGrid",{8,8}},"Embeddings"]

Select[gs,!DegenerateGraphEmbeddingQ[#]&]

gs=Drop[gs,2];

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubeConnectedCycle",4},"VertexList"],GraphData[{"CubeConnectedCycle",4},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"CubeConnectedCycle",4},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,,,,};

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubeConnectedCycle",4}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,,,};

Matchstick

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

3D default

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

3D All

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

{"CubeConnectedCycle", 5}

GraphData[{"CubeConnectedCycle",5},"StandardName"]

Primary

GraphData[{"CubeConnectedCycle",5}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubeConnectedCycle",5},"EdgeList"]]

Default embedding

g=Graph[GraphData[{"CubeConnectedCycle",5},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubeConnectedCycle",5},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubeConnectedCycle",5},"Graph","Degenerate"]

Bilateral

GraphData[{"CubeConnectedCycle",5},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubeConnectedCycle",5},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubeConnectedCycle",5},"Planar"]

GraphData[{"CubeConnectedCycle",5},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubeConnectedCycle",5},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubeConnectedCycle",5},"Circulant"]

GraphData[{"CubeConnectedCycle",5},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubeConnectedCycle",5},"Halin"]

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

Rigid

GraphData[{"CubeConnectedCycle",5},"Rigid"]

GraphData[{"CubeConnectedCycle",5},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubeConnectedCycle",5},"Flexible"]

GraphData[{"CubeConnectedCycle",5},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubeConnectedCycle",5},"LCF"]

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

GraphData[{"CubeConnectedCycle",5},"LCFSignature"]

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

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

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

LCF compute random

ComputeRandomLCFNotation[{"CubeConnectedCycle",5},2,TimeConstraint->120]

lcf={{{-59,19,-27,-4,-56,-33,-59,19,16,4,-39,39,33,-4,4,27,41,-41,-4,4,-19,59,13,-4,-16,7,-19,59,56,44,41,-41,-7,-44,4,-13,41,-41,-4,4},4}};

g=LCFGraph[Sequence@@lcf[[1]],-22]

BilateralLCFGraph@@@lcf

l={{{"CubeConnectedCycle",5},{0,Missing["NotAvailable",lcf]}}}

PropertyReplace[l,"LCFNotations","13.3"]

RenameGraphFiles[]

LCF compute 10^5

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

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

MaxMemoryUsed[]/10.^9 "GB"

LCF compute 10^6

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

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

lcfs={{{-59,19,-27,-4,-56,-33,-59,19,16,4,-39,39,33,-4,4,27,41,-41,-4,4,-19,59,13,-4,-16,7,-19,59,56,44,41,-41,-7,-44,4,-13,41,-41,-4,4},4},{{-72,-52,-51,-7,-10,-66,-22,-69,72,-22,69,4,-22,-18,7,-4,-70,-69,69,66,12,-7,11,-26,22,-27,70,22,69,52,22,51,-12,-11,10,18,7,26,27,-69},4}};

l={{{"CubeConnectedCycle",5},{0,Missing["NotAvailable",lcfs]}}}

PropertyReplace[l,"LCFNotations","13.3"]

RenameGraphFiles[]

gs=LCFGraph[Sequence@@#,#2]&@@@Transpose[{lcfs,{55,-7}}]

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

DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]//Timing

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

LCF compute 10^7

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

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

UnitDistance

GraphData[{"CubeConnectedCycle",5},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubeConnectedCycle",5},"VertexList"],GraphData[{"CubeConnectedCycle",5},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"CubeConnectedCycle",5},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubeConnectedCycle",5}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

3D default

Graph3D[GraphData[{"CubeConnectedCycle",5},"Edges"]]

3D All

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

{"CubeConnectedCycle", 6}

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

Primary

GraphData[{"CubeConnectedCycle",6}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubeConnectedCycle",6},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubeConnectedCycle",6},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubeConnectedCycle",6},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubeConnectedCycle",6},"Graph","Degenerate"]

Bilateral

GraphData[{"CubeConnectedCycle",6},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubeConnectedCycle",6},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubeConnectedCycle",6},"Planar"]

GraphData[{"CubeConnectedCycle",6},"Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubeConnectedCycle",6},"Circulant"]

GraphData[{"CubeConnectedCycle",6},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubeConnectedCycle",6},"Halin"]

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

Rigid

GraphData[{"CubeConnectedCycle",6},"Rigid"]

GraphData[{"CubeConnectedCycle",6},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubeConnectedCycle",6},"Flexible"]

GraphData[{"CubeConnectedCycle",6},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubeConnectedCycle",6},"LCF"]

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

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

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

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

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

LCF compute random

ComputeRandomLCFNotation[{"CubeConnectedCycle",6},2,TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

Length[gs]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

UnitDistance

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

3D default

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

3D All

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

{"CubeConnectedCycle", 7}

GraphData[{"CubeConnectedCycle",7},"StandardName"]

All

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

Halin

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

LCF

GraphData[{"CubeConnectedCycle",7},"LCFSignature"]

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

UnitDistance

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"CubeConnectedCycle",7},{"RCN","CN"}]

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

Default embedding

g=Graph@GraphData[{"CubeConnectedCycle",7},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"CubeConnectedCycle",7}]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"CubeConnectedCycle",7},"Edges"]]

3D All

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

{"CubeConnectedCycle", 8}

GraphData[{"CubeConnectedCycle",8},"StandardName"]

All

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

Halin

GraphData[{"CubeConnectedCycle",8},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CubeConnectedCycle",8},"LCFSignature"]

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

UnitDistance

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"CubeConnectedCycle",8},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

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

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

Default embedding

g=Graph@GraphData[{"CubeConnectedCycle",8},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"CubeConnectedCycle",8}]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

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

3D All

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

Cayley

3

GraphData[{"CubeConnectedCycle",3},"CayleyGraphGeneratingGroups"]

GraphData[{"CubeConnectedCycle",4},"CayleyGraphGeneratingGroups"]

GraphData[{"CubeConnectedCycle",3},"#"]

t=Tuples[{0,1},3]

g1=Flatten[Position[t,#]&/@(RotateRight/@t)]

g2=Flatten[Position[t,#]&/@(RotateLeft/@t)]

g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]

g=PermutationGroup[PermutationCycles/@{g1,g2,g3}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

4

t=Tuples[{0,1},4];

g=PermutationGroup[PermutationCycles/@{
g1=Flatten[Position[t,#]&/@(RotateRight/@t)],
g2=Flatten[Position[t,#]&/@(RotateLeft/@t)],
g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

IsomorphicGraphQ[cg,System`Graph[Edges[MyCubeConnectedCycle[4]]]]

5

t=Tuples[{0,1},5];

g=PermutationGroup[PermutationCycles/@{
g1=Flatten[Position[t,#]&/@(RotateRight/@t)],
g2=Flatten[Position[t,#]&/@(RotateLeft/@t)],
g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

IsomorphicGraphQ[cg,System`Graph[Edges[MyCubeConnectedCycle[5]]]]

6

t=Tuples[{0,1},6];

g=PermutationGroup[PermutationCycles/@{
g1=Flatten[Position[t,#]&/@(RotateRight/@t)],
g2=Flatten[Position[t,#]&/@(RotateLeft/@t)],
g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

7

t=Tuples[{0,1},7];

g=PermutationGroup[PermutationCycles/@{
g1=Flatten[Position[t,#]&/@(RotateRight/@t)],
g2=Flatten[Position[t,#]&/@(RotateLeft/@t)],
g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

8

t=Tuples[{0,1},8];

g=PermutationGroup[PermutationCycles/@{
g1=Flatten[Position[t,#]&/@(RotateRight/@t)],
g2=Flatten[Position[t,#]&/@(RotateLeft/@t)],
g3=Flatten[Position[t,#]&/@(Prepend[Rest[#],1-#[[1]]]&/@t)]}]

cg=UndirectedGraph[CayleyGraph[g]]

RecognizeGraph[cg]

GraphData

GraphClassString

GraphClassString[Table[GraphData[{"CubeConnectedCycle",d},"#"],{d,3,6}]]

GraphDataString

SortBy[GraphData["CubeConnectedCycle"],GraphData[#,"V"]&]

MyCubeConnectedCycle[1]//ShowGraph

RecognizeGraph/@Table[MyCubeConnectedCycle[n],{n,8}]

GetGraphData[{"CubeConnectedCycle",4},"File","8.1"]

file=OpenAppend["~/CubeConnectedCycle.m",PageWidth->Infinity]

Do[WriteString[file,GraphDataString[MyCubeConnectedCycle[n],
"StandardName"->{"CubeConnectedCycle",n},
"Name"->ToString[n]<>"\\[Hyphen]cube connected cycle graph",
"NotationRules"->{"CubeConnectedCycle"->n},
"Classes"->{"Cayley","CubeConnectedCycle"},
"Vertices"->None,
"Skip"->{"Line"},
"Information"->"Cube-ConnectedCycle",
TimeConstraint->60,
Debug->True
]],{n,5,8}]

Close[file]