Empty Graph

Author

Eric W. Weisstein
August 2, 2023

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

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

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

Figure

Built-in

GraphicsGrid[Partition[Table[System`Graph[Range[n],{},VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black],{n,10}],UpTo[5]],Dividers->All]

GraphData default (circular)

GraphicsGrid[Partition[Table[GraphData[{"Empty",n}]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,10}],UpTo[5]],Dividers->All]

GraphData "Circular"

GraphicsGrid[Partition[Table[GraphData[{"Empty",n},"Graph","Circular"][[1]]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,10}],UpTo[5]],Dividers->All]

GraphData "Grid"

GraphicsGrid[Partition[Table[GraphData[{"Empty",n},"Graph","Grid"][[1]]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,10}],UpTo[5]],Dividers->All]

GraphData "Linear"

GraphicsGrid[Partition[Table[GraphData[{"Empty",n},"Graph","Linear"][[1]]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,10}],UpTo[5]],Dividers->All]

GraphData "TriangularGrid"

GraphicsGrid[Partition[Table[GraphData[{"Empty",n},"Graph","TriangularGrid"][[1]]/.g_System`Graph:>SetProperty[g,{VertexSize->If[n==1,.01,{"Scaled",.05}],System`VertexStyle->Red,System`EdgeStyle->Black}],{n,30}],UpTo[5]],Dividers->All]

Graphics

a=1.1;
Show[GraphicsArray[Table[
Graphics[{Line[{{-a,-a},{-a,a},{a,a},{a,-a},{-a,-a}}],PointSize[.05],Point/@If[i==1,{{0,0}},CircularVertices[i]]},PlotRange->All,AspectRatio->Automatic],
{i,5}]],GraphicsSpacing->.2]

Classes

Intersection@@GraphData["Empty","Classes"]

GraphClassesThatAreClass["Empty"]

Embeddings

EmptyEmbedding[n_]:=Module[{m=Ceiling[Sqrt[n]]},Sort[Reverse/@Flatten[MapIndexed[{m,0}+({-1,1}#2)&,Partition[Range[n],m,m,{1,1},{}],{2}],1]]
]

EmptyEmbedding2[n_]:={{#-(n+1)/2.,0.}&/@Range[n],EmptyEmbedding[n]}

Print[{#,EmptyEmbedding[#]}]&/@Range[3,20];

Graphics[Point[#],Frame->True,FrameTicks->None,PlotRangePadding->.1,ImagePadding->1]&/@EmptyEmbedding/@Range[3,20]

Print[{#,EmptyEmbedding2[#]}]&/@Range[21,30];

Properties

Acyclic

Table[GraphData[{"Empty",n},"Acyclic"],{n,30}]

AdjacencyMatrixCount

seq=Table[GraphData[{"Empty",n},"AdjacencyMatrixCount"],{n,30}]

Arboricity

Table[GraphData[{"Empty",n},"Arboricity"],{n,30}]

ArcTransitive

Table[GraphData[{"Empty",n},"ArcTransitive"],{n,30}]

ArcTransitivity

Table[GraphData[{"Empty",n},"ArcTransitivity"],{n,30}]

AutomorphismCount

seq=Table[GraphData[{"Empty",n},"AutomorphismCount"],{n,30}]

FindSequenceFunction[seq,n]

BalabanIndex

Table[GraphData[{"Empty",n},"BalabanIndex"],{n,30}]

Bandwidth

Table[GraphData[{"Empty",n},"Bandwidth"],{n,30}]

BridgeCount

seq=Table[GraphData[{"Empty",n},"BridgeCount"],{n,30}]

BurningNumber

seq=Table[GraphData[{"Empty",n},"BurningNumber"],{n,30}]

CharacteristicPolynomial

seq=Table[GraphData[{"Empty",n},"CharacteristicPolynomial"][x],{n,30}]

FindSequenceFunction[seq,n]

ChordCount

seq=Table[GraphData[{"Empty",n},"ChordCount"],{n,30}]

ChordlessCycleCount

seq=Table[GraphData[{"Empty",n},"ChordlessCycleCount"],{n,30}]

FindSequenceFunction[seq,n]

ChromaticInvariant

seq=Table[GraphData[{"Empty",n},"ChromaticInvariant"],{n,30}]

FindSequenceFunction[Rest@seq,n-1]

ChromaticNumber

seq=Table[GraphData[{"Empty",n},"ChromaticNumber"],{n,30}]

Circumference

seq=Table[GraphData[{"Empty",n},"Circumference"],{n,30}]

FindSequenceFunction[Drop[seq,2],n]

Classes

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

CliqueCount

seq=Table[GraphData[{"Empty",n},"CliqueCount"],{n,30}]

CliqueCoveringNumber

seq=Table[GraphData[{"Empty",n},"CliqueCoveringNumber"],{n,30}]

CliqueNumber

seq=Table[GraphData[{"Empty",n},"CliqueNumber"],{n,30}]

CliquePolynomial

(poly=Factor@Table[GraphData[{"Empty",n},"CliquePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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]

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

FullSimplify[%-poly]

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"Empty",n},"ComplementOddChordlessCycleCount"],{n,30}]

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

ConnectedComponentCount

seq=Table[GraphData[{"Empty",n},"ConnectedComponentCount"],{n,30}]

ConnectedDominatingSetCount

seq=Table[GraphData[{"Empty",n},"ConnectedDominatingSetCount"],{n,30}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationNumber

seq=Table[GraphData[{"Empty",n},"ConnectedDominationNumber"],{n,30}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationPolynomial

(poly=Factor@Table[GraphData[{"Empty",n},"ConnectedDominationPolynomial"][x],{n,k0=1,20}])//Column

ConnectedDominationNumber

seq=Table[GraphData[{"Empty",n},"ConnectedDominationNumber"],{n,30}]

FindSequenceFunction[seq,n]

ConnectedInducedSubgraphCount

seq=Table[GraphData[{"Empty",n},"ConnectedInducedSubgraphCount"],{n,30}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Empty",n},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=1,kmax=30}],_Missing[x]])

CrossingNumber

seq=Table[GraphData[{"Empty",n},"CrossingNumber"],{n,30}]

CycleCount

seq=Table[GraphData[{"Empty",n},"CycleCount"],{n,30}]

CyclePolynomial

(poly=Factor@Table[GraphData[{"Empty",n},"CyclePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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]

Table[((((x^(2 n))-n ((x^2)-1)-1)(x^4) )/((((x^2)-1))^2)),{n,10}]//Factor

FullSimplify[%-poly]

Cyclic

Table[GraphData[{"Empty",n},"Cyclic"],{n,30}]

CyclomaticNumber

seq=Table[GraphData[{"Empty",n},"CyclomaticNumber"],{n,30}]

DetourIndex

seq=Table[GraphData[{"Empty",n},"DetourIndex"],{n,30}]

DetourMatrix

seq=Table[GraphData[{"Empty",n},"DetourMatrix"],{n,5}]

Normal/@Table[SparseArray[{i_,i_}:>0,{n,n},Infinity],{n,5}]

Normal/@Table[SparseArray[{Band[{1,1}]->0},{n,n},Infinity],{n,5}]

DetourPolynomial

(poly=Factor@Table[GraphData[{"Empty",n},"DetourPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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]

Table[((((x^(2 n))-n ((x^2)-1)-1)(x^4) )/((((x^2)-1))^2)),{n,10}]//Factor

FullSimplify[%-poly]

Diameter

seq=Table[GraphData[{"Empty",n},"Diameter"],{n,30}]

DistinguishingNumber

seq=Table[GraphData[{"Empty",n},"DistinguishingNumber"],{n,30}]

DominatingSetCount

seq=Table[GraphData[{"Empty",n},"DominatingSetCount"],{n,30}]

DominationNumber

seq=Table[GraphData[{"Empty",n},"DominationNumber"],{n,30}]

DominationPolynomial

seq=Table[GraphData[{"Empty",n},"DominationPolynomial"],{n,30}]

EdgeChromaticNumber

seq=Table[GraphData[{"Empty",n},"EdgeChromaticNumber"],{n,30}]

EdgeConnectivity

Table[GraphData[{"Empty",n},"EdgeConnectivity"],{n,30}]

EdgeCount

seq=Table[GraphData[{"Empty",n},"EdgeCount"],{n,30}]

EdgeCoverCount

seq=Table[GraphData[{"Empty",n},"EdgeCoverCount"],{n,30}]

EdgeCoverNumber

seq=Table[GraphData[{"Empty",n},"EdgeCoverNumber"],{n,30}]

EulerianCycleCount

seq=Table[GraphData[{"Empty",n},"EulerianCycleCount"],{n,30}]

FaceCount

seq=Table[GraphData[{"Empty",n},"FaceCount"],{n,30}]

FibonacciCube

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

seq=Table[GraphData[{"Empty",n},"FibonacciCube"],{n,30}]

FlowPolynomial

(poly=Factor@Table[GraphData[{"Empty",n},"FlowPolynomial"][x],{n,k0=1,10}])//Column

FractionalChromaticNumber

seq=Table[GraphData[{"Empty",n},"FractionalChromaticNumber"],{n,30}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"Empty",n},"FractionalEdgeChromaticNumber"],{n,30}]

Girth

seq=Table[GraphData[{"Empty",n},"Girth"],{n,30}]

Gonality

seq=Table[GraphData[{"Empty",n},"Gonality"],{n,30}]

HamiltonConnected

seq=Table[GraphData[{"Empty",n},"HamiltonConnected"],{n,30}]

HamiltonDecompositionCount

seq=Table[GraphData[{"Empty",n},"HamiltonDecompositionCount"],{n,30}]

Hamiltonian

Table[GraphData[{"Empty",n},"Hamiltonian"],{n,30}]

HamiltonianCycleCount

seq=Table[GraphData[{"Empty",n},"HamiltonianCycleCount"],{n,30}]

HamiltonianNumber

seq=Table[GraphData[{"Empty",n},"HamiltonianNumber"],{n,30}]

HamiltonianPathCount

seq=Table[GraphData[{"Empty",n},"HamiltonianPathCount"],{n,30}]

HamiltonianWalkCount

seq=Table[GraphData[{"Empty",n},"HamiltonianWalkCount"],{n,30}]

HararyIndex

seq=Table[GraphData[{"Empty",n},"HararyIndex"],{n,30}]

HexagonCount

seq=Table[GraphData[{"Empty",n},"HexagonCount"],{n,30}]

IdiosyncraticPolynomial

(poly=Table[GraphData[{"Empty",n},"IdiosyncraticPolynomial"][x,y],{n,10}])//Column

Table[(x-(n-1) y) (x+y)^(n-1),{n,10}]

Simplify[Abs[%/poly]]

IncidenceMatrix

seq=Table[GraphData[{"Empty",n},"IncidenceMatrix"],{n,30}]

IndependenceNumber

seq=Table[GraphData[{"Empty",n},"IndependenceNumber"],{n,30}]

IndependenceRatio

seq=Table[GraphData[{"Empty",n},"IndependenceRatio"],{n,30}]

IndependentEdgeSetCount

seq=Table[GraphData[{"Empty",n},"IndependentEdgeSetCount"],{n,30}]

IndependentVertexSetCount

A000079

seq=Table[GraphData[{"Empty",n},"IndependentVertexSetCount"],{n,30}]

FindSequenceFunction[seq,n]

seq=2^Range[0,20]

FindLinearRecurrence[seq]

LinearRecurrence[{2},{2},{0,20}]

FindGeneratingFunction[seq,x]

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

IntersectionNumber

seq=Table[GraphData[{"Empty",n},"IntersectionNumber"],{n,30}]

IrredundantSetCount

seq=Table[GraphData[{"Empty",n},"IrredundantSetCount"],{n,30}]

FindSequenceFunction[DeleteMissing@seq,n]

KirchhoffIndex

seq=Table[GraphData[{"Empty",n},"KirchhoffIndex"],{n,30}]

KirchhoffSumIndex

seq=Table[GraphData[{"Empty",n},"KirchhoffSumIndex"],{n,30}]

LeafCount

seq=Table[GraphData[{"Empty",n},"LeafCount"],{n,30}]

LongestCycleCount

seq=Table[GraphData[{"Empty",n},"LongestCycleCount"],{n,30}]

LovaszNumber

seq=Table[GraphData[{"Empty",n},"LovaszNumber"],{n,30}]

LucasCube

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

seq=Table[GraphData[{"Empty",n},"LucasCube"],{n,30}]

MatchingGeneratingPolynomial

poly=Table[GraphData[{"Empty",n},"MatchingGeneratingPolynomial"][x],{n,30}]

MatchingNumber

seq=Table[GraphData[{"Empty",n},"MatchingNumber"],{n,30}]

MatchingPolynomial

poly=Table[GraphData[{"Empty",n},"MatchingPolynomial"][x],{n,30}]

MaximalCliqueCount

seq=Table[GraphData[{"Empty",n},"MaximalCliqueCount"],{n,30}]

MaximalIndependentEdgeSetCount

seq=Table[GraphData[{"Empty",n},"MaximalIndependentEdgeSetCount"],{n,30}]

MaximalIndependentVertexSetCount

seq=Table[GraphData[{"Empty",n},"MaximalIndependentVertexSetCount"],{n,30}]

MaximalIrredundantSetCount

seq=Table[GraphData[{"Empty",n},"MaximalIrredundantSetCount"],{n,30}]

MaximumCliqueCount

seq=Table[GraphData[{"Empty",n},"MaximumCliqueCount"],{n,30}]

MaximumIndependentEdgeSetCount

seq=Table[GraphData[{"Empty",n},"MaximumIndependentEdgeSetCount"],{n,30}]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"Empty",n},"MaximumIndependentVertexSetCount"],{n,30}]

MaximumLeafNumber

seq=Table[GraphData[{"Empty",n},"MaximumLeafNumber"],{n,30}]

MaximumVertexDegree

seq=Table[GraphData[{"Empty",n},"MaximumVertexDegree"],{n,30}]

MeanDistance

seq=Table[GraphData[{"Empty",n},"MeanDistance"],{n,30}]

MinimalDominatingSetCount

seq=Table[GraphData[{"Empty",n},"MinimalDominatingSetCount"],{n,30}]

MinimalDominatingSetSignature

seq=Table[GraphData[{"Empty",n},"MinimalDominatingSetSignature"],{n,30}]

MinimumCliqueCoveringCount

seq=Table[GraphData[{"Empty",n},"MinimumCliqueCoveringCount"],{n,30}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"Empty",n},"MinimumConnectedDominatingSetCount"],{n,30}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"Empty",n},"MinimumDistinguishingLabelingCount"],{n,30}]

FindSequenceFunction[seq,n]

MinimumDominatingSetCount

seq=Table[GraphData[{"Empty",n},"MinimumDominatingSetCount"],{n,30}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"Empty",n},"MinimumEdgeCoverCount"],{n,30}]

MinimumVertexDegree

seq=Table[GraphData[{"Empty",n},"MinimumVertexDegree"],{n,30}]

MolecularTopologicalIndex

seq=Table[GraphData[{"Empty",n},"MolecularTopologicalIndex"],{n,30}]

Nonhamiltonian

Table[GraphData[{"Empty",n},"Nonhamiltonian"],{n,30}]

OddChordlessCycleCount

seq=Table[GraphData[{"Empty",n},"OddChordlessCycleCount"],{n,30}]

PathCount

seq=Table[GraphData[{"Empty",n},"PathCount"],{n,30}]

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[{"Empty",n},"PathPolynomial"],{n,k0=1,kmax=30}]/.f_Function:>f[x]])

Pell

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

seq=Table[GraphData[{"Empty",n},"Pell"],{n,30}]

PentagonCount

seq=Table[GraphData[{"Empty",n},"PentagonCount"],{n,30}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Drop[seq,2],n]

FindGeneratingFunction[seq,x]

FindLinearRecurrence[seq]

Perfect

Table[GraphData[{"Empty",n},"Perfect"],{n,30}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"Empty",n},"ProjectivePlaneCrossingNumber"],{n,30}]

Radius

seq=Table[GraphData[{"Empty",n},"Radius"],{n,30}]

RankPolynomial

seq=Table[GraphData[{"Empty",n},"RankPolynomial"],{n,10}]

RectilinearCrossingNumber

seq=Table[GraphData[{"Empty",n},"RectilinearCrossingNumber"],{n,30}]

SigmaPolynomial

A008278

(poly=Factor@Table[GraphData[{"Empty",n},"SigmaPolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

Table[StirlingS2[n,m](x^(n-m)),{n,10},{m,n}]

Table[Sum[StirlingS2[n,m](x^(n-m)),{m,n}],{n,10}]//Column

Sum[StirlingS2[n,m](x^(n-m)),{m,n}]//FullSimplify

Table[(x^n) BellB[n,(1/x)]//Expand,{n,10}]==poly

Table[CoefficientList[(x^n) BellB[n,(1/x)],x],{n,10}]//Flatten

With[{n=10},CoefficientList[(x^n) BellB[n,(1/x)],x]]

Skewness

seq=Table[GraphData[{"Empty",n},"Skewness"],{n,30}]

SpanningTreeCount

seq=Table[GraphData[{"Empty",n},"SpanningTreeCount"],{n,30}]

SquareCount

seq=Table[GraphData[{"Empty",n},"SquareCount"],{n,30}]

StabilityIndex

seq=Table[GraphData[{"Empty",n},"StabilityIndex"],{n,30}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

TopologicalIndex

seq=Table[GraphData[{"Empty",n},"TopologicalIndex"],{n,30}]

ToroidalCrossingNumber

seq=Table[GraphData[{"Empty",n},"ToroidalCrossingNumber"],{n,30}]

Traceable

Table[GraphData[{"Empty",n},"Traceable"],{n,30}]

TriangleCount

seq=Table[GraphData[{"Empty",n},"TriangleCount"],{n,30}]

TuttePolynomial

seq=Table[GraphData[{"Empty",n},"TuttePolynomial"],{n,10}]

Untraceable

Table[GraphData[{"Empty",n},"Untraceable"],{n,30}]

VertexConnectivity

Table[GraphData[{"Empty",n},"VertexConnectivity"],{n,30}]

VertexCount

seq=Table[GraphData[{"Empty",n},"VertexCount"],{n,30}]

VertexCoverNumber

Related to but not the same as IndependenceNumber

seq=Table[GraphData[{"Empty",n},"VertexCoverNumber"],{n,30}]

VertexCoverPolynomial

seq=Table[GraphData[{"Empty",n},"VertexCoverPolynomial"][x],{n,10}]//Column

VertexDegrees

seq=Table[GraphData[{"Empty",n},"VertexDegrees"],{n,30}]

WienerIndex

seq=Table[GraphData[{"Empty",n},"WienerIndex"],{n,30}]

WienerSumIndex

seq=Table[GraphData[{"Empty",n},"WienerSumIndex"],{n,30}]

FindSequenceFunction[seq,n]

GraphData

GraphClassString

GraphClassString[GraphData["Empty"]]