Mycielski Graph

Author

Eric W. Weisstein
August 2, 2023

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

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

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

Graphic

GraphicsRow[Table[Show[GraphData[{"Mycielski",n}]//StyleGraphs,PlotLabel->Column[{
Subscript[M,n],
GraphData[{"Mycielski",n},"Name"]
}/.s_String:>Style[s,Italic],Alignment->Center,BaseStyle->{14,Black,FontFamily->"Times"}]],{n,4}],ImageSize->700,Alignment->Top,Dividers->All]

Special cases

TextGrid[Sort[{"Mycielski"/.GraphData[#,"NotationRules"],GraphData[#,"V"],GraphData[#,"Name"]}&/@DeleteCases[GraphData["Mycielski"],{"Mycielski",_}]],Dividers->All,Alignment->{{{Decimal},Left}}]

Embeddings

{"Mycielski", 1} == "SingletonGraph"

GraphData[{"Mycielski",1},"StandardName"]

{"Mycielski", 2} == {"Path", 2}

GraphData[{"Mycielski",2},"StandardName"]

{"Mycielski", 3} == {"Cycle", 5}

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

{"Mycielski", 4} == "GroetzschGraph"

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

{"Mycielski", 5}

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

GraphPlot@GraphData[{"Mycielski",5},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Mycielski",5}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Mycielski",5}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

Table[MinimalCrossingGraph[GraphData[{"Mycielski",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[{"Mycielski",5},"Circulant"]

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Mycielski",5},"Matchstick"]

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Mycielski",5},"Polyhedral"]

GraphData[{"Mycielski",5},"Graph",{"3D","Polyhedron"}]

Triangle-Free graphs with chromatic number k having smallest number of vertices

tf=Sort[GraphData[#,{"ChromaticNumber","V","#"}]&/@GraphData["TriangleFree"]];

c=Split[tf,First[#1]==First[#2]&];

TextGrid[{#[[1,1]],Take[l=Sort[Rest/@#],Min[10,Length[l]]]}&/@Take[c,10],Dividers->All]

Table[If[n==1,1,3 (2^(n-2))-1],{n,10}]

Properties

Acyclic

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

AdjacencyMatrixCount

seq=Table[GraphData[{"Mycielski",n},"AdjacencyMatrixCount"],{n,8}]

Table[((Piecewise[{{3 2^(n-2)-1,n>1}},1]!)/(Piecewise[{{1,n==1},{2,n==2}},10])),{n,8}]

FullSimplify[((Piecewise[{{3 2^(n-2)-1,n>1}},1]!)/(Piecewise[{{1,n==1},{2,n==2}},10]))]

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

Arboricity

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

ArcTransitive

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

ArcTransitivity

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

AutomorphismCount

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

BalabanIndex

Table[GraphData[{"Mycielski",n},"BalabanIndex"],{n,4}]//FullSimplify

Bandwidth

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

BridgeCount

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

BurningNumber

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

Possibly 1, 2, 3, ...

ChordlessCycleCount

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

ChromaticInvariant

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

ChromaticNumber

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

Circumference

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

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

Classes

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

CliqueCount

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

FindSequenceFunction[seq,n]//FunctionExpand

FindGeneratingFunction[seq,x]

SeriesCoefficient[%x,{x,0,n}]//FullSimplify

Table[%,{n,11}]

Table[(1/18) (9+7 (3^n)),{n,11}]

CliqueCoveringNumber

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

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

gf=x FindGeneratingFunction[seq,x]

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

Table[3 (2^(n-3)),{n,11}]

CliqueNumber

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

ComplementOddChordlessCycleCount

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

FindSequenceFunction[Take[seq,{3,5}],n]

ConnectedDominatingSetCount

A287432

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

ConnectedDominationNumber

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

ConnectedDominationPolynomial

(poly=Factor[Table[GraphData[{"Mycielski",n},"ConnectedDominationPolynomial"],{n,k0=1,kmax=11}]/.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,20}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A290766

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

FindSequenceFunction[DeleteMissing[seq],n]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Mycielski",n},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=1,kmax=11}],_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]

CrossingNumber

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

CycleCount

A234625

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

Cyclic

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

CyclomaticNumber

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

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

Table[(1/18) (45-27 (2^n)+7 (3^n)),{n,11}]

DetourIndex

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

FindSequenceFunction[{1,35,550,5566,49726},n]

FindGeneratingFunction[{1,35,550,5566,49726},x]

Diameter

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

DistinguishingNumber

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

DomaticNumber

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

Table[Piecewise[{{2,n==3||n==4},{4,n==5}},n],{n,11}]

%==seq

Do[Print[{n,DomaticNumber[GraphData[{"Mycielski",n}]]//Timing}],{n,4}]

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

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

Table[Floor[Divide@@GraphData[{"Mycielski",n},{"VertexCount","DominationNumber"}]],{n,10}]

DominatingSetCount

A290872

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

DominationNumber

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

EdgeChromaticNumber

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

FindSequenceFunction[seq,n]

FunctionExpand[%]

FindGeneratingFunction[seq,x]

SeriesCoefficient[x((x-2 (x^3)+2 (x^4))/(1-3 x+2 (x^2))),{x,0,n}]//FullSimplify

Table[-1+3 (2^(-3+n)),{n,11}]

EdgeConnectivity

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

EdgeCount

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

FindSequenceFunction[%,n]

FunctionExpand[%]

FindGeneratingFunction[seq,x]

SeriesCoefficient[x((-x+(x^2)-(x^3))/(-1+6 x-11 (x^2)+6 (x^3))),{x,0,n}]//FullSimplify

Table[(1/36) (18-27 (2^n)+14 (3^n)),{n,11}]

Expand[(1/36) (18-27 (2^n)+14 (3^n))]

EdgeCoverCount

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

EdgeCoverNumber

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

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

EulerianCycleCount

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

FaceCount

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

FibonacciCube

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

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

FractionalChromaticNumber

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

RSolve[{a[n]==a[n-1]+1/a[n-1],a[1]==1},a[n],n]

RecurrenceTable[{a[n]==a[n-1]+1/a[n-1],a[1]==1},a,{n,7}]

FractionalEdgeChromaticNumber

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

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

Table[3 2^(n-3)-1,{n,11}]

Girth

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

Hamiltonian

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

HamiltonConnected

Jarnicki et al. 2017: HC for all k except k=3

Table[GraphData[{"Mycielski",n},"HamiltonConnected"],{n,10}]

HamiltonDecompositionCount

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

HamiltonianCycleCount

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

HamiltonianNumber

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

Table[-1+3 (2^(-2+n)),{n,11}]

HamiltonianPathCount

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

HamiltonianWalkCount

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

HararyIndex

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

FindSequenceFunction[seq,n]//FunctionExpand

FindGeneratingFunction[seq,x]

SeriesCoefficient[((2 x-5 (x^2)-5 (x^3)-(x^4))/(2 (1-10 x+35 (x^2)-50 (x^3)+24 (x^4))))x,{x,0,n}]//FullSimplify

SeriesCoefficient[((2 x-5 (x^2)-5 (x^3)-(x^4))/(2 (1-10 x+35 (x^2)-50 (x^3)+24 (x^4)))),{x,0,n}]//FullSimplify

Table[(3/4)-15 (2^(-4+n))+((7 (3^(-2+n)))/4)+9 (4^(-3+n)),{n,11}]

Table[(1/48)(36-45 (2^n)+28 (3^(n-1))+27 (4^(n-1))),{n,11}]

HexagonCount

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

FindSequenceFunction[seq,n]

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

FindGeneratingFunction[seq,x]

HosoyaIndex

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

IndependenceNumber

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

FindSequenceFunction[seq,n]

FunctionExpand[%]

FindGeneratingFunction[seq,x]

SeriesCoefficient[x((1-2 x+(x^2)+(x^3))/(1-3 x+2 (x^2))),{x,0,n}]//FullSimplify

Table[%,{n,11}]

Table[-1+3 (2^(-3+n)),{n,11}]

IndependenceRatio

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

FindSequenceFunction[%,n]

Table[((Piecewise[{{3 2^(n-3)-1,n>2}},1])/(Piecewise[{{3 2^(n-2)-1,n>1}},1])),{n,11}]

FullSimplify[((Piecewise[{{3 2^(n-3)-1,n>2}},1])/(Piecewise[{{3 2^(n-2)-1,n>1}},1])),n>2]

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

Table[Piecewise[{{1,n==1},{1/2,n==2}},(1/2)+(2/(4-3 (2^n)))],{n,11}]

IndependentEdgeSetCount

A293240

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

FindSequenceFunction[DeleteMissing@seq,n]

IndependentVertexSetCount

A292710

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

FindLinearRecurrence[Rest@seq]

FindSequenceFunction[DeleteMissing@seq,n]

FindGeneratingFunction[DeleteMissing@seq,x]

IntersectionNumber

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

KirchhoffIndex

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

FindSequenceFunction[%,n]

KirchhoffSumIndex

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

LeafCount

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

LongestCycleCount

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

LovaszNumber

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

LucasCube

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

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

MatchingNumber

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

MaximalCliqueCount

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

FindSequenceFunction[seq,n]//FunctionExpand

SeriesCoefficient[FindGeneratingFunction[seq,x],{x,0,n}]

Table[(1/6) (3-9 (2^(n-1))+7 (3^(n-1))),{n,11}]

MaximalIndependentEdgeSetCount

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

MaximalIndependentVertexSetCount

A290609

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

MaximumCliqueCount

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

FindSequenceFunction[seq,n]//FunctionExpand

SeriesCoefficient[FindGeneratingFunction[seq,x],{x,0,n}]

Table[(1/6) (3-9 (2^(n-1))+7 (3^(n-1))),{n,11}]

MaximumIndependentEdgeSetCount

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

MaximumIndependentVertexSetCount

Possibly 1 for n > 3?

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

MaximumLeafNumber

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

MaximumVertexDegree

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

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

MeanDistance

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

MinimalDominatingSetCount

A290871

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

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

FindSequenceFunction[DeleteMissing@seq,n]

MinimalDominatingSetSignature

seq=Table[GraphData[{"Mycielski",n},"MinimalDominatingSetSignature"],{n,11}]//Column

MinimumCliqueCoveringCount

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

MinimumConnectedDominatingSetCount

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

FindSequenceFunction[DeleteMissing[seq],n]

MinimumDistinguishingLabelingCount

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

MinimumDominatingSetCount

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

MinimumEdgeCoverCount

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

MinimumVertexCoverCount

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

MinimumVertexDegree

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

MolecularTopologicalIndex

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]//Factor

-36(3·(2^n)-8)(27·(2^n)-(143^n)-18)

Table[(3 2^n-8)(14 3^n-27 2^n+18)/36,{n,11}]

Nonhamiltonian

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

OddChordlessCycleCount

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

PathCount

seq=Table[GraphData[{"Mycielski",n},"PathCount"],{n,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[{"Mycielski",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",{"Mycielski",n}]["Pell"]

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

PentagonCount

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

FindSequenceFunction[seq,n]

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

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

ProjectivePlaneCrossingNumber

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

Radius

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

RectilinearCrossingNumber

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

SpanningTreeCount

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

FindSequenceFunction[Take[seq,7],n]

FindGeneratingFunction[Take[seq,7],x]

SquareCount

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

FindSequenceFunction[seq,n]

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

FindGeneratingFunction[seq,x]

FindLinearRecurrence[Drop[seq,3]]

StabilityIndex

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

FindSequenceFunction[%,n]

FindGeneratingFunction[seq,x]

TopologicalIndex

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

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

Traceable

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

TriangleCount

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

Untraceable

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

VertexConnectivity

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

VertexCoverCount

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

FindSequenceFunction[Drop[seq,-4]]

x FindGeneratingFunction[DeleteMissing[seq],x]

VertexCoverNumber

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

FindSequenceFunction[seq,n]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

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

Table[3 (2^(-3+n)),{n,11}]

VertexCount

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

FindSequenceFunction[%,n]

FunctionExpand[%]

FindGeneratingFunction[seq,x]

SeriesCoefficient[((1-x+(x^2))/(1-3 x+2 (x^2))),{x,0,n}]

3 2^(Range[10]-2)-1

VertexDegrees

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

VertexTransitive

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

WienerIndex

A292055

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

FindSequenceFunction[seq,n]

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

seq=Table[If[n==1,0,(216-27 (2^(n+3))-56 (3^n)+81 (4^n))/144],{n,30}]

coef=FindLinearRecurrence[Rest@seq]

Join[{0},LinearRecurrence[{10,-35,50,-24},{1,15,90,435},20]]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((x (1+5 x-25 (x^2)+10 (x^3)))/(1-10 x+35 (x^2)-50 (x^3)+24 (x^4))),{x,0,20}],x]

WienerSumIndex

seq=Table[GraphData[{"Mycielski",n},"WienerSumIndex"],{n,5}]

FindSequenceFunction[seq,n]

Construction

Compare with Combinatorica

CMycielskiGraph[1]:=CompleteGraph[1]
CMycielskiGraph[2]:=CompleteGraph[2]
CMycielskiGraph[3]:=Cycle[5]
CMycielskiGraph[4]:=GroetzschGraph
CMycielskiGraph[k_Integer]:=Module[{g=MycielskiGraph[k-1],al,n,i},n=V[g];
al=ToAdjacencyLists[g];
FromAdjacencyLists[Join[Map[Join[#,n+#]&,al],Table[Append[al[[i]],2n+1],{i,n}],{Range[n+1,2n]}]]]/;(k>4)

ToEntity[CombinatoricaGraphToV8Graph@MycielskiGraph[4]]

ToEntity[CombinatoricaGraphToV8Graph@MycielskiGraph[5]]

Built-in

Clear[MyMycielskiGraph]

MyMycielskiGraph[1]:=System`CompleteGraph[1]
MyMycielskiGraph[2]:=System`CompleteGraph[2]
MyMycielskiGraph[3]:=CycleGraph[5]

MyFromAdjacencyLists[l_]:=System`Graph[Union[Flatten[l]],UndirectedEdge@@@Union[Sort/@Flatten[MapIndexed[Thread[{#2[[1]],#}]&,l],1]]]

MyMycielskiGraph[k_Integer?Positive]:=MyMycielskiGraph[k]=Module[{g=MyMycielskiGraph[k-1],al,n,i},n=VertexCount[g];
al=AdjacencyList[g,#]&/@VertexList[g];
MyFromAdjacencyLists[Join[Map[Join[#,n+#]&,al],Table[Append[al[[i]],2n+1],{i,n}],{Range[n+1,2n]}]]]

ToEntity/@MyMycielskiGraph/@Range[11]

GraphData

GraphClassString

GraphClassString[GraphData["Mycielski"]]

GraphDataString

Do[Print[GraphDataString[MycielskiGraph[n],{{"Mycielski",n},ToString[n]<>"-Mycielski graph","MycielskiGraph"},TimeConstraint->60]],{n,10}]