Erdos Sequence

Author

Eric W. Weisstein
March 11, 2024

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

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

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

Source

https://mathoverflow.net/questions/17875/can-every-finite-graph-be-represented-by-an-arithmetic-sequence-of-natural-numbe

Figure

<<MathWorld`Graphs`

ErdosLabeledGraph[l_,opts___?OptionQ]:=Module[
{
g,v,
size=Lookup[{opts},"VertexLabelSize",18],
plotlabel=Lookup[{opts},PlotLabel,None],
r,
style
},
style=Directive[Background->White,FontFamily->"Times",Black];
g=ErdosGraph[l,VertexLabelStyle->Directive[size,style]]//StyleGraphs;
v=ToCommonEdges[GraphData[r=RecognizeGraph@g],g];
If[plotlabel===Automatic,plotlabel=Style[GraphData[r,"Notation"]/.c_String?(StringMatchQ[#,LetterCharacter]&):>Style[c,Italic],style,18]];
Annotate[g,{VertexCoordinates->v,PlotLabel->plotlabel}]
]

ErdosLabeledGraph[{2,3,5,6,10,15}]//StyleGraphs

GraphicsGrid[Partition[ErdosLabeledGraph[#,"VertexLabelSize"->12,PlotLabel->Automatic]&/@{{1,2},{2,4},{1,2,3},{2,3,6},{2,4,6},{2,3,5,30},{2,4,6,8},{3,5,6,10},{10,14,15,21},{2,3,5,7,210},{6,10,14,15,21}},UpTo[4]],Dividers->All,Alignment->Center,ImageSize->700]

Minimum value by n

Table[Min[DeleteMissing[GraphData[#,"ErdosSequence"]&/@GraphData[n]]],{n,10}]

Table[Times@@Prime[Range[n-1]],{n,10}]

GraphData[#,{"#","ErdosSequence"}]&/@GraphData[2]

Select[GraphData[5],Max[GraphData[#,"ErdosSequence"]]==210&]

Select[GraphData[6],Max[GraphData[#,"ErdosSequence"]]==2310&]

Maximum value by n

A002110

Table[Max[DeleteMissing[GraphData[#,"ErdosSequence"]&/@GraphData[n]]],{n,10}]

Table[Times@@Prime[Range[n-1]],{n,10}]

GraphData[#,{"#","ErdosSequence"}]&/@GraphData[2]

Select[GraphData[5],Max[GraphData[#,"ErdosSequence"]]==210&]

Select[GraphData[6],Max[GraphData[#,"ErdosSequence"]]==2310&]

Disconnected

ErdosGraph[GraphData[#,"ErdosSequence"]]&/@GraphData["K4+C3+P2+K1","ConnectedComponents","Name"]

ErdosGraph@GraphData["C3+P2+K1","ErdosSequence"]

Contains isolated point

one=Select[GraphData[All],MemberQ[GraphData[#,"ErdosSequence"],1]&]

Select[GraphData[All],ListQ[GraphData[#,"ErdosSequence"]]&&GraphData[#,"MinimumVertexDegree"]==0&]==one

Parametrized families

Alkane

Table[GraphData[{"Alkane",n},"ErdosSequence"],{n,10}]//Column

AlternatingGroupGraph

Table[GraphData[{"AlternatingGroupGraph",n},"ErdosSequence"],{n,2,6}]//Column

Andrasfai

Table[GraphData[{"Andrasfai",n},"ErdosSequence"],{n,20}]//Column

Antelope n×n

Table[GraphData[{"Antelope",{n,n}},"ErdosSequence"],{n,20}]//Column

Antiprism

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

Table[GraphData[{"Antiprism",n},"ErdosSequence"],{n,3,25}]//Column

Apollonian

Table[GraphData[{"Apollonian",n},"ErdosSequence"],{n,5}]//Column

Barbell

Table[GraphData[{"Barbell",n},"ErdosSequence"],{n,3,20}]//Column

BlackBishop n×n

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"BlackBishop",{n,n}},"ErdosSequence"],{n,3}]//StyleGraphs,Dividers->All]

Table[GraphData[{"BlackBishop",{n,n}},"ErdosSequence"],{n,20}]//Column

Bishop n×n

GraphicsRow[GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Bishop",{n,n}},"ErdosSequence"],{n,2}]//StyleGraphs],Dividers->All]

Table[GraphData[{"Bishop",{n,n}},"ErdosSequence"],{n,20}]//Column

Book

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Book",n},"ErdosSequence"],{n,1}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Book",n},"ErdosSequence"],{n,20}]//Column

Bruhat

Table[GraphData[{"Bruhat",n},"ErdosSequence"],{n,6}]//Column

Camel n×n

Table[GraphData[{"Camel",{n,n}},"ErdosSequence"],{n,20}]//Column

Centipede

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Centipede",n},"ErdosSequence"],{n,2}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Centipede",n},"ErdosSequence"],{n,10}]//Column

CocktailParty

Table[GraphData[{"CocktailParty",n},"ErdosSequence"],{n,20}]//Column

Complete

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Complete",n},"ErdosSequence"],{n,5}]//StyleGraphs[#,VertexSize->{"Scaled",.1}]&,Dividers->All]

Table[GraphData[{"Complete",n},"ErdosSequence"],{n,30}]//Column

Do[Print[{gn={"Complete",n},ErdosSequence[GraphData[gn]]//Timing}],{n,8}]

CompleteBipartite n×n

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"CompleteBipartite",{n,n}},"ErdosSequence"],{n,2}]//StyleGraphs,Dividers->All]

Table[GraphData[{"CompleteBipartite",{n,n}},"ErdosSequence"],{n,20}]//Column

CompleteBipartite m×n

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

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

CompleteTripartite n×n×n

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

Table[GraphData[{"CompleteTripartite",{n,n,n}},"ErdosSequence"],{n,10}]//Column

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"ErdosSequence"],
3Max[k,m,n]/2
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

Table[GraphData[{"CrossedPrism",2n},"ErdosSequence"],{n,2,12}]//Column

Crown

Table[GraphData[{"Crown",n},"ErdosSequence"],{n,20}]//Column

CubeConnectedCycle

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

Table[GraphData[{"CubeConnectedCycle",n},"ErdosSequence"],{n,3,8}]//Column

Cycle

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

A370654

RadiallyLabeledGraph[g0_]:=Module[{g=IndexGraph@g0,vl,v,e,lab},
vl=VertexList[g];
v=GraphEmbedding[g];
e=List@@@EdgeList[g];
lab=Sort[Rule[#,Placed[#2,"Circular"]]&@@@Lookup[Options[g],VertexLabels]];
Graph[vl,e,VertexLabels->lab,BaseStyle->Directive[14,FontFamily->"Times"]]
]

GraphicsGrid[Partition[RadiallyLabeledGraph/@ErdosGraph/@Table[GraphData[{"Cycle",n},"ErdosSequence"],{n,3,10}]//StyleGraphs,UpTo[4]],Dividers->All,ImageSize->800]

(seq=Table[GraphData[{"Cycle",n},"ErdosSequence"],{n,3,30}])//Column

2+Length@DeleteMissing@seq

Length[Flatten[DeleteMissing@seq]]

BFile[Flatten[DeleteMissing@seq],370654,3,"~/b370654.txt"]

DeleteMissing[seq][[All,-1]]

FindSequenceFunction[DeleteMissing@seq]//Head

FactorInteger/@seq//Column

Do[Print[{gn={"Cycle",n},ErdosSequence[GraphData[gn],MaxIterations->40,Debug->True]//Timing,MaxMemoryUsed[]/10^9.}],{n,3,5}]

Do[Print[{gn={"Cycle",n},ErdosSequence[GraphData[gn],Debug->True]//Timing,MaxMemoryUsed[]/10^9.}],{n,{6}}]

Compute from pairs of primes

CycleGraphErdosSequence[n_]:=Module[
{pairs=Times@@@Subsets[Prime[Range[n]],{2}],subs,can=Hash@CanonicalGraph[CycleGraph[n]],erdos},
subs=Subsets[pairs,{n}];
erdos=Sort[Select[subs,Hash@CanonicalGraph[ErdosGraph[#,VertexLabels->None]]===can&]];
Sort[SortBy[erdos,Max][[1]]]
]

Do[Print[{gn={"Cycle",n},CycleGraphErdosSequence[n]//Timing,MaxMemoryUsed[]/10^9.}],{n,3,10}]

l={
{{"Cycle",13},{0,{34,62,87,111,155,205,247,253,259,287,299,319,323}}}
};

Pari

row(n)=if(n<4, if(n==3, [2, 4, 6]), my(v=[oo]); forperm(primes(n), p, my(t=vecsort(vector(#p, k, p[k]*if(k==1, p[#p], p[k-1])))); if(t[#t] < v[#v] || (t[#t] == v[#v] && lex(t, v)<0), v=t)); v)

#
? print(row(5))
[10, 21, 22, 33, 35]
cpu time = 1 ms, real time = 1 ms.

? print(row(6))
[14, 26, 33, 35, 39, 55]
cpu time = 5 ms, real time = 6 ms.

? print(row(7))
[14, 34, 39, 51, 55, 65, 77]
cpu time = 28 ms, real time = 29 ms.

? print(row(8))
[22, 38, 51, 57, 65, 77, 85, 91]
cpu time = 235 ms, real time = 236 ms.

? print(row(9))
[22, 34, 39, 69, 95, 115, 119, 133, 143]
cpu time = 2,325 ms, real time = 2,332 ms.

? print(row(10))
[26, 38, 51, 87, 115, 133, 143, 145, 161, 187]
cpu time = 25,554 ms, real time = 25,973 ms.

? print(row(11));
[26, 46, 57, 87, 115, 155, 187, 203, 209, 217, 221]
cpu time = 5min, 6,766 ms, real time = 5min, 10,405 ms.

? print(row(12));
[34, 58, 69, 111, 155, 185, 203, 209, 217, 221, 247, 253]
cpu time = 1h, 6min, 42,033 ms, real time = 1h, 8min, 20,941 ms.

? print(row(13));
[34, 62, 87, 111, 155, 205, 247, 253, 259, 287, 299, 319, 323]
cpu time = 15h, 25min, 44,417 ms, real time = 15h, 37min, 7,199 ms.

CycleComplement

Table[GraphData[{"CycleComplement",n},"ErdosSequence"],{n,3,20}]//Column

DiagonalIntersection

Table[GraphData[{"DiagonalIntersection",n},"ErdosSequence"],{n,3,14}]//Column

Dipyramid

Table[GraphData[{"Dipyramid",n},"ErdosSequence"],{n,3,20}]//Column

DorogovtsevGoltsevMendes

Table[GraphData[{"DorogovtsevGoltsevMendes",n},"ErdosSequence"],{n,0,7}]//Column

DoubleCone

Table[GraphData[{"DoubleCone",n},"ErdosSequence"],{n,3,20}]//Column

Empty

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Empty",n},"ErdosSequence"],{n,5}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Empty",n},"ErdosSequence"],{n,30}]//Column

Do[Print[{gn={"Empty",n},ErdosSequence[GraphData[gn]]//Timing}],{n,10}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"ErdosSequence"],{n,15}]//Column

Fiveleaper n×n

Table[GraphData[{"Fiveleaper",{n,n}},"ErdosSequence"],{n,20}]//Column

Flower

Table[GraphData[{"Flower",n},"ErdosSequence"],{n,5,20}]//Column

FoldedCube

Table[GraphData[{"FoldedCube",n},"ErdosSequence"],{n,2,10}]//Column

Gear

Table[GraphData[{"Gear",n},"ErdosSequence"],{n,3,20}]//Column

Giraffe n×n

Table[GraphData[{"Giraffe",{n,n}},"ErdosSequence"],{n,20}]//Column

Goldberg

Table[GraphData[{"Goldberg",n},"ErdosSequence"],{n,3,20}]//Column

Grid n×n

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

Table[GraphData[{"Grid",{n,n}},"ErdosSequence"],{n,20}]//Column

Grid m×n

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

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

Grid n×n×n

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

Table[GraphData[{"Grid",{n,n,n}},"ErdosSequence"],{n,10}]//Column

Grid k×m×n

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

Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"ErdosSequence"],
XXX
},{n,5},{m,n},{k,m}],2]

HalvedCube

Table[GraphData[{"HalvedCube",n},"ErdosSequence"],{n,10}]//Column

Hanoi

Table[GraphData[{"Hanoi",n},"ErdosSequence"],{n,5}]//Column

Helm

Table[GraphData[{"Helm",n},"ErdosSequence"],{n,3,20}]//Column

Hypercube

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Hypercube",n},"ErdosSequence"],{n,0,2}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Hypercube",n},"ErdosSequence"],{n,0,10}]//Column

Keller

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

Table[GraphData[{"Keller",n},"ErdosSequence"],{n,5}]//Column

FindSequenceFunction[seq,n]

King n×n

Table[GraphData[{"King",{n,n}},"ErdosSequence"],{n,20}]//Column

King m×n

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

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

Knight n×n

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

Table[GraphData[{"Knight",{n,n}},"ErdosSequence"],{n,20}]//Column

Do[Print[{gn={"Knight",{n,n}},ErdosSequence[GraphData[gn]]//Timing}],{n,10}]

Knight m×n

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

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

Ladder

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

Table[GraphData[{"Ladder",n},"ErdosSequence"],{n,20}]//Column

Do[Print[{gn={"Ladder",n},ErdosSequence[GraphData[gn]]//Timing}],{n,10}]

LadderRung

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"LadderRung",n},"ErdosSequence"],{n,2}]//StyleGraphs,Dividers->All]

Table[GraphData[{"LadderRung",n},"ErdosSequence"],{n,20}]//Column

Do[Print[{gn={"LadderRung",n},ErdosSequence[GraphData[gn]]//Timing}],{n,10}]

LucasCube

Table[GraphData[{"LucasCube",n},"ErdosSequence"],{n,15}]//Column

MengerSponge

Table[GraphData[{"MengerSponge",n},"ErdosSequence"],{n,3}]//Column

MoebiusLadder

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

Table[GraphData[{"MoebiusLadder",n},"ErdosSequence"],{n,3,25}]//Column

Mycielski

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

Table[GraphData[{"Mycielski",n},"ErdosSequence"],{n,11}]//Column

Odd

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

Table[GraphData[{"Odd",n},"ErdosSequence"],{n,7}]//Column

Pan

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Pan",n},"ErdosSequence"],{n,3,3}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Pan",n},"ErdosSequence"],{n,3,20}]//Column

Path

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

GraphicsGrid[Partition[ErdosLabeledGraph/@Table[GraphData[{"Path",n},"ErdosSequence"],{n,6}]//StyleGraphs,UpTo[3]],Dividers->All,ImageSize->700]

Table[GraphData[{"Path",n},"ErdosSequence"],{n,20}]//Column

Do[Print[{gn={"Path",n},ErdosSequence[GraphData[gn]]//Timing}],{n,10}]

PathComplement

Table[GraphData[{"PathComplement",n},"ErdosSequence"],{n,20}]//Column

Pell

Table[GraphData[{"Pell",n},"ErdosSequence"],{n,9}]//Column

Prism

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

Table[GraphData[{"Prism",n},"ErdosSequence"],{n,3,25}]//Column

Queen n×n

Table[GraphData[{"Queen",{n,n}},"ErdosSequence"],{n,20}]//Column

Rook n×n

Table[GraphData[{"Rook",{n,n}},"ErdosSequence"],{n,20}]//Column

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"ErdosSequence"],{n,20}]//Column

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"ErdosSequence"],{n,4}]//Column

SierpinskiGasket

Table[GraphData[{"SierpinskiGasket",n},"ErdosSequence"],{n,5}]//Column

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"ErdosSequence"],{n,6}]//Column

Spoke n×n

Table[GraphData[{"Spoke",{n,n}},"ErdosSequence"],{n,5}]//Column

StackedBook

Table[GraphData[{"StackedBook",{n,n}},"ErdosSequence"],{n,10}]//Column

StackedPrism

Table[GraphData[{"StackedPrism",{n,n}},"ErdosSequence"],{n,3,5}]//Column

Star

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Star",n},"ErdosSequence"],{n,5}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Star",n},"ErdosSequence"],{n,25}]//Column

Do[Print[{gn={"Star",n},ErdosSequence[GraphData[gn]]//Timing}],{n,4}]

f[1]:={1}
f[2]:={2,4}
f[n_]:=Module[{ps=Prime[Range[n-1]]},Append[ps,Times@@ps]]

RecognizeGraph/@Table[ErdosGraph[f[n]],{n,10}]

Sun

Table[GraphData[{"Sun",n},"ErdosSequence"],{n,3,20}]//Column

Sunlet

Table[GraphData[{"Sunlet",n},"ErdosSequence"],{n,3,20}]//Column

TorusGrid n×n

Table[GraphData[{"TorusGrid",{n,n}},"ErdosSequence"],{n,3,20}]//Column

Transposition

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

Table[GraphData[{"Transposition",n},"ErdosSequence"],{n,6}]//Column

Trapezohedron

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

Table[GraphData[{"Trapezohedron",n},"ErdosSequence"],{n,3,20}]//Column

Triangular

Table[GraphData[{"Triangular",n},"ErdosSequence"],{n,2,20}]//Column

TriangularGrid

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"TriangularGrid",n},"ErdosSequence"],{n,0,2}]//StyleGraphs,Dividers->All]

Table[GraphData[{"TriangularGrid",n},"ErdosSequence"],{n,0,20}]//Column

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ErdosSequence"],{n,20}]//Column

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"ErdosSequence"],{n,20}]//Column

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ErdosSequence"],{n,20}]//Column

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"ErdosSequence"],{n,20}]//Column

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"ErdosSequence"],{n,20}]//Column

Do[Print[{gn={"TriangularHoneycombRook",n},ErdosSequence[GraphData[gn]]//Timing,MaxMemoryUsed[]/10^9.}],{n,8}]

TriangularSnake

Table[GraphData[{"TriangularSnake",n},"ErdosSequence"],{n,1,20,2}]//Column

Web

Table[GraphData[{"Web",n},"ErdosSequence"],{n,3,20}]//Column

Wheel

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

GraphicsRow[ErdosLabeledGraph/@Table[GraphData[{"Wheel",n},"ErdosSequence"],{n,4,5}]//StyleGraphs,Dividers->All]

Table[GraphData[{"Wheel",n},"ErdosSequence"],{n,4,20}]//Column

Do[Print[{gn={"Wheel",n},ErdosSequence[GraphData[gn]]//Timing}],{n,4,5}]

Compute from primes

WheelGraphErdosSequence[n_]:=Module[
{pairs=Times@@@Subsets[Prime[Range[n-1]],{2}],subs,can=Hash@CanonicalGraph[WheelGraph[n]],erdos},
subs=Subsets[pairs,{n}];
erdos=Sort[Select[subs,Hash@CanonicalGraph[ErdosGraph[#,VertexLabels->None]]===can&]];
SortBy[erdos,Max][[1]]
]

WheelGraphErdosSequence[5]

WheelComplement

Table[GraphData[{"WheelComplement",n},"ErdosSequence"],{n,4,20}]//Column

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"ErdosSequence"],{n,2,20}]//Column

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"ErdosSequence"],{n,20}]//Column

Small examples

1

SequenceGraph[#,VertexLabels->Automatic]&/@Subsets[Range[3],{2}]

2

RecognizeGraph/@DeleteDuplicatesBy[SequenceGraph[#,VertexLabels->Automatic]&/@Subsets[Range[20],{2}],CanonicalGraph]

Complement[GraphData[2],%]

Print[{#,ErdosSequence[GraphData[#]]//Timing}]&/@GraphData[2];

3

RecognizeGraph/@DeleteDuplicatesBy[ErdosGraph/@Subsets[Range[20],{3}],CanonicalGraph]

Complement[GraphData[3],%]

Print[{#,ErdosSequence[GraphData[#]]//Timing}]&/@GraphData[3];

4

(r=RecognizeGraph/@DeleteDuplicatesBy[SequenceGraph[#,VertexLabels->Automatic]&/@Subsets[Range[30],{4}],CanonicalGraph])//Timing

Complement[GraphData[4],r]

Print[{#,ErdosSequence[GraphData[#]]//Timing}]&/@GraphData[4];

5

(r=RecognizeGraph/@DeleteDuplicatesBy[SequenceGraph[#,VertexLabels->Automatic]&/@Subsets[Range[35],{5}],CanonicalGraph])//Timing

Complement[GraphData[5],r]

Print[{#,ErdosSequence[GraphData[#]]//Timing}]&/@GraphData[5];

ErdosGraph[{2,33,35,42,55},VertexLabelStyle->Directive[FontFamily->"Times",18]]

RecognizeGraph@%

6

ErdosGraph[{2,3,5,6,10,15},VertexLabelStyle->Directive[Background->White,FontFamily->"Times",18]]//StyleGraphs

Checks

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

Missing

TextGrid[Table[{n,Intersection[GraphData[n],GraphData["ErdosSequence","Missing"]]},{n,9}],Dividers->All]

Batch compute

Code

ErdosSequenceSearch[nmax_,kmax_,known_:{},opts___?OptionQ]:=ErdosSequenceSearch[{1,nmax},kmax,known,opts]

ErdosSequenceSearch[{nmin_,nmax_},kmax_,known_:{},opts___?OptionQ]:=Module[
{
n,graphs,k=1,new,
debug=Lookup[{opts},Debug,False],
t,max
},
If[debug,t=AbsoluteTime[]];
Do[
max=Min[kmax,If[n==2,4,Times@@Prime[Range[n-1]]]];
If[debug,Print[n,"/",max,", subsets: ",Binomial[kmax,n],", dt: ",AbsoluteTime[]-t,", maxmem: ",MaxMemoryUsed[]/10^9.," GB"]];
graphs=DeleteDuplicatesBy[
{
RecognizeGraph[CanonicalGraph[ErdosGraph[#]],"Cache"->"InternalOnly"],
#
}&/@Subsets[Range[max],{n}],
First
];
new=Select[graphs,FreeQ[#[[1]],{}|Alternatives@@known]&];
Print[new],
{n,nmin,nmax}
]
]

known=Select[GraphData[;;10],ListQ[GraphData[#,"ErdosSequence"]]&]

Compute new

ErdosSequenceSearch[{10},30,known,Debug->True]

ErdosSequenceSearch[10,30,known,Debug->True]

ErdosSequenceSearch[9,40,known,Debug->True]

ErdosSequenceSearch[{5,9},50,known,Debug->True]

Batch

DateString[]

ErdosSequenceSearch[10,50,known,Debug->True]

[eww@byblis65 Batch]$ /Developer/eww/Mathematica/M-LINUX-L/14.1.0.0/current/Executables/math < ErdosSequence.m > Logs/ErdosSequence.log &

ErdosSequenceSearch[10, 50, known, Debug -> True]
{}
3/6, subsets: 19600, dt: 0.681135, maxmem: 0.279474 GB
{}
4/30, subsets: 230300, dt: 0.690736, maxmem: 0.279474 GB
{}
5/50, subsets: 2118760, dt: 15.379380, maxmem: 0.279474 GB
{}
6/50, subsets: 15890700, dt: 1225.536823, maxmem: 0.68792 GB
{}
7/50, subsets: 99884400, dt: 10763.113099, maxmem: 3.57204 GB
{}
8/50, subsets: 536878650, dt: 75014.827204, maxmem: 21.8584 GB

No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry