Star Graph

Author

Eric W. Weisstein
August 2, 2023

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

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

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

Graphics

Graphs.m

GraphicsGrid[Partition[Table[Show[StarGraph[n,VertexSize->If[n==1,.017,{"Scaled",.07}],System`VertexStyle->Red,System`EdgeStyle->Black],PlotLabel->Style[Subscript[S,n],FontFamily->"Times"]],{n,8}],UpTo[4]],ImageSize->400,Dividers->All]

GraphData

GraphicsGrid[Partition[Show[GraphData[{"Star",#}]/.g_System`Graph:>SetProperty[g,{VertexSize->If[#==1,.017,{"Scaled",.07}],System`VertexStyle->Red,System`EdgeStyle->Black}],PlotLabel->Style[Subscript[S,#],FontFamily->"Times"]]&/@Range[8],4],ImageSize->400,Dividers->All]

Testing

Table[Select[ConnectedGraphs[n],StarGraphQ],{n,5}]

Isomorphism

ToEntity/@Table[System`CompleteGraph[{n-1,1}],{n,2,10}]

ToEntity/@Table[StarGraph[n],{n,10}]

Properties

Acyclic

Table[GraphData[{"Star",n},"Acyclic"],{n,25}]

AdjacencyMatrixCount

seq=Table[GraphData[{"Star",n},"AdjacencyMatrixCount"],{n,25}]

Arboricity

Table[GraphData[{"Star",n},"Arboricity"],{n,25}]

ArcTransitive

Table[GraphData[{"Star",n},"ArcTransitive"],{n,25}]

ArcTransitivity

Table[GraphData[{"Star",n},"ArcTransitivity"],{n,25}]

AutomorphismCount

seq=Table[GraphData[{"Star",n},"AutomorphismCount"],{n,25}]

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

Table[Gamma[n],{n,25}]

BalabanIndex

seq=Table[GraphData[{"Star",n},"BalabanIndex"],{n,25}]^2

FindSequenceFunction[seq,n]//Factor

Table[Sqrt[(n-1)^3/(2 n-3)],{n,25}]

Bandwidth

Table[GraphData[{"Star",n},"Bandwidth"],{n,25}]

Table[Floor[n/2],{n,25}]

BridgeCount

seq=Table[GraphData[{"Star",n},"BridgeCount"],{n,25}]

BurningNumber

seq=Table[GraphData[{"Star",n},"BurningNumber"],{n,25}]

ChordCount

seq=Table[GraphData[{"Star",n},"ChordCount"],{n,25}]

ChordlessCycleCount

seq=Table[GraphData[{"Star",n},"ChordlessCycleCount"],{n,25}]

ChromaticallyUnique

seq=Table[GraphData[{"Star",n},"ChromaticallyUnique"],{n,25}]

GraphData[{"ChromaticallyUnique","Star"}]

Subtract@@@Table[GraphData[{#,n},"ChromaticPolynomial"][x]&/@{"Path","Star"},{n,20}]

ChromaticInvariant

seq=Table[GraphData[{"Star",n},"ChromaticInvariant"],{n,25}]

ChromaticNumber

seq=Table[GraphData[{"Star",n},"ChromaticNumber"],{n,25}]

Circumference

seq=Table[GraphData[{"Star",n},"Circumference"],{n,25}]

Classes

new=Intersection@@(GraphData[#,"Classes"]&/@GraphData["Star"])

old={"Acyclic","Apex","Bicolorable","Bipartite","Cactus","Caterpillar","Chordal","Chordless","Class1","Connected","EdgeTransitive","Forest","Lobster","Perfect","Planar","Pseudoforest","Pseudotree","Simple","SquareFree","Star","StronglyPerfect","Tree","TriangleFree","UnitDistance","WeaklyPerfect"};

Complement[old,new]

CliqueCount

seq=Table[GraphData[{"Star",n},"CliqueCount"],{n,25}]

CliqueCoveringNumber

seq=Table[GraphData[{"Star",n},"CliqueCoveringNumber"],{n,25}]

CliqueNumber

seq=Table[GraphData[{"Star",n},"CliqueNumber"],{n,25}]

CochromaticGraphNames

Table[MemberQ[GraphData[{"Star",n},"CochromaticGraphNames"],{"Path",n}],{n,25}]

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

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"Star",n},"ComplementOddChordlessCycleCount"],{n,25}]

ConnectedDominatingSetCount

seq=Table[GraphData[{"Star",n},"ConnectedDominatingSetCount"],{n,25}]

FindLinearRecurrence[Drop[seq,2]]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

gf=x FindGeneratingFunction[seq,x]

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

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

ConnectedDominationNumber

seq=Table[GraphData[{"Star",n},"ConnectedDominationNumber"],{n,25}]

ConnectedDominationPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Star",n},"ConnectedDominationPolynomial"][x],{n,k0=1,kmax=25}],_Missing[x]])//Column

ConnectedInducedSubgraphCount

A006127

seq=Table[GraphData[{"Star",n},"ConnectedInducedSubgraphCount"],{n,25}]

FindSequenceFunction[DeleteCases[seq,_Missing],n]//FullSimplify

ConnectedInducedSubgraphPolynomial

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

FullSimplify[poly2-poly]

CrossingNumber

seq=Table[GraphData[{"Star",n},"CrossingNumber"],{n,25}]

CycleCount

seq=Table[GraphData[{"Star",n},"CycleCount"],{n,25}]

Cyclic

Table[GraphData[{"Star",n},"Cyclic"],{n,25}]

CyclomaticNumber

seq=Table[GraphData[{"Star",n},"CyclomaticNumber"],{n,25}]

DetourIndex

seq=Table[GraphData[{"Star",n},"DetourIndex"],{n,25}]

FindSequenceFunction[seq,n]

Diameter

seq=Table[GraphData[{"Star",n},"Diameter"],{n,25}]

DistinguishingNumber

seq=Table[GraphData[{"Star",n},"DistinguishingNumber"],{n,25}]

DomaticNumber

seq=Table[GraphData[{"Star",n},"DomaticNumber"],{n,25}]

System`StarGraph[5,VertexLabels->"Name"]

Table[DomaticNumber[g=System`StarGraph[n]],{n,6}]

Piecewise[{{1,n==1}},2]

DominatingSetCount

seq=Table[GraphData[{"Star",n},"DominatingSetCount"],{n,25}]

FindSequenceFunction[seq,n]

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

DominationNumber

seq=Table[GraphData[{"Star",n},"DominationNumber"],{n,25}]

EdgeChromaticNumber

seq=Table[GraphData[{"Star",n},"EdgeChromaticNumber"],{n,25}]

EdgeConnectivity

Table[GraphData[{"Star",n},"EdgeConnectivity"],{n,25}]

EdgeCount

seq=Table[GraphData[{"Star",n},"EdgeCount"],{n,25}]

EdgeCoverCount

seq=Table[GraphData[{"Star",n},"EdgeCoverCount"],{n,25}]

EdgeCoverNumber

seq=Table[GraphData[{"Star",n},"EdgeCoverNumber"],{n,25}]

EulerianCycleCount

seq=Table[GraphData[{"Star",n},"EulerianCycleCount"],{n,25}]

FaceCount

seq=Table[GraphData[{"Star",n},"FaceCount"],{n,25}]

FibonacciCube

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

seq=Table[GraphData[{"Star",n},"FibonacciCube"],{n,25}]

FractionalChromaticNumber

seq=Table[GraphData[{"Star",n},"FractionalChromaticNumber"],{n,25}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"Star",n},"FractionalEdgeChromaticNumber"],{n,25}]

Gonality

seq=Table[GraphData[{"Star",n},"Gonality"],{n,25}]

Girth

seq=Table[GraphData[{"Star",n},"Girth"],{n,25}]

HamiltonConnected

seq=Table[GraphData[{"Star",n},"HamiltonConnected"],{n,25}]

HamiltonDecompositionCount

seq=Table[GraphData[{"Star",n},"HamiltonDecompositionCount"],{n,25}]

Hamiltonian

Table[GraphData[{"Star",n},"Hamiltonian"],{n,25}]

HamiltonianCycleCount

seq=Table[GraphData[{"Star",n},"HamiltonianCycleCount"],{n,25}]

HamiltonianNumber

seq=Table[GraphData[{"Star",n},"HamiltonianNumber"],{n,25}]

FindSequenceFunction[seq,n]

HamiltonianPathCount

seq=Table[GraphData[{"Star",n},"HamiltonianPathCount"],{n,25}]

HamiltonianWalkCount

seq=Table[GraphData[{"Star",n},"HamiltonianWalkCount"],{n,25}]

FindSequenceFunction[{1,3,12,60,360,2520,20160},n]//FunctionExpand

Table[Piecewise[{{Missing["NotAvailable"],n==1},{1,n==2||n==3}},Gamma[n-1]/2],{n,25}]

HararyIndex

seq=Table[GraphData[{"Star",n},"HararyIndex"],{n,25}]

FindSequenceFunction[seq,n]

HexagonCount

seq=Table[GraphData[{"Star",n},"HexagonCount"],{n,25}]

Hypohamiltonian

Table[GraphData[{"Star",n},"Hypohamiltonian"],{n,25}]

Hypotraceable

Table[GraphData[{"Star",n},"Hypotraceable"],{n,25}]

IndependenceNumber

seq=Table[GraphData[{"Star",n},"IndependenceNumber"],{n,25}]

IndependenceRatio

seq=Table[GraphData[{"Star",n},"IndependenceRatio"],{n,25}]

FindSequenceFunction[Rest@seq,n-1]

IndependentEdgeSetCount

seq=Table[GraphData[{"Star",n},"IndependentEdgeSetCount"],{n,25}]

IndependentVertexSetCount

A000051

seq=Table[GraphData[{"Star",n},"IndependentVertexSetCount"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

FindLinearRecurrence[seq]

LinearRecurrence[{3,-2},{2,3},20]

IntersectionNumber

seq=Table[GraphData[{"Star",n},"IntersectionNumber"],{n,25}]

KirchhoffIndex

seq=Table[GraphData[{"Star",n},"KirchhoffIndex"],{n,25}]

FindSequenceFunction[seq,n]

KirchhoffSumIndex

seq=Table[GraphData[{"Star",n},"KirchhoffSumIndex"],{n,25}]

FindSequenceFunction[seq,n]

Binomial[n,2]

LeafCount

seq=Table[GraphData[{"Star",n},"LeafCount"],{n,25}]

LongestCycleCount

seq=Table[GraphData[{"Star",n},"LongestCycleCount"],{n,25}]

LovaszNumber

seq=Table[GraphData[{"Star",n},"LovaszNumber"],{n,25}]

LucasCube

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

seq=Table[GraphData[{"Star",n},"LucasCube"],{n,25}]

MatchingGeneratingPolynomial

poly=Table[GraphData[{"Star",n},"MatchingGeneratingPolynomial"][x],{n,25}]

Table[Sum[Piecewise[{{1,k==0},{n-1,k==1}},0](x^k),{k,0,Floor[n/2]}],{n,5}]

poly2=Table[1+(n-1) x,{n,25}]

poly-poly2

expr=Sum[Piecewise[{{1,k==0},{n-1,k==1}},0](x^k),{k,0,Floor[n/2]}]

Table[expr,{n,5}]

...wrong...

MatchingNumber

seq=Table[GraphData[{"Star",n},"MatchingNumber"],{n,25}]

MatchingPolynomial

poly=Table[GraphData[{"Star",n},"MatchingPolynomial"][x],{n,25}]

k-Matchings

Piecewise[{{1,k==0},{n-1,k==1}},0]

Table[Sum[(((-1))^k)Piecewise[{{1,k==0},{n-1,k==1}},0](x^(n-2k)),{k,0,Floor[n/2]}],{n,5}]

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

expr=Sum[(((-1))^k)Piecewise[{{1,k==0},{n-1,k==1}},0](x^(n-2k)),{k,0,Floor[n/2]}]

Table[expr,{n,5}]

...wrong...

MaximalCliqueCount

seq=Table[GraphData[{"Star",n},"MaximalCliqueCount"],{n,25}]

MaximalIndependentEdgeSetCount

seq=Table[GraphData[{"Star",n},"MaximalIndependentEdgeSetCount"],{n,25}]

MaximalIndependentVertexSetCount

seq=Table[GraphData[{"Star",n},"MaximalIndependentVertexSetCount"],{n,25}]

MaximalIrredundantSetCount

seq=Table[GraphData[{"Star",n},"MaximalIrredundantSetCount"],{n,25}]

MaximumCliqueCount

seq=Table[GraphData[{"Star",n},"MaximumCliqueCount"],{n,25}]

MaximumIndependentEdgeSetCount

seq=Table[GraphData[{"Star",n},"MaximumIndependentEdgeSetCount"],{n,25}]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"Star",n},"MaximumIndependentVertexSetCount"],{n,25}]

MaximumLeafNumber

seq=Table[GraphData[{"Star",n},"MaximumLeafNumber"],{n,25}]

MaximumVertexDegree

seq=Table[GraphData[{"Star",n},"MaximumVertexDegree"],{n,25}]

MeanDistance

seq=Table[GraphData[{"Star",n},"MeanDistance"],{n,25}]

FindSequenceFunction[seq,n]//Factor

MinimalDominatingSetCount

seq=Table[GraphData[{"Star",n},"MinimalDominatingSetCount"],{n,25}]

MinimalDominatingSetSignature

(seq=Table[GraphData[{"Star",n},"MinimalDominatingSetSignature"],{n,25}])//Column

MinimalEdgeCoverCount

seq=Table[GraphData[{"Star",n},"MinimalEdgeCoverCount"],{n,25}]

GraphData[{"Star",4},"MinimalEdgeCovers"]

GraphData[{"Empty",1},"MinimalEdgeCovers"]

MinimalEdgeCoverSignature

seq=Table[GraphData[{"Star",n},"MinimalEdgeCoverSignature"],{n,25}]//Column

MinimumCliqueCoveringCount

seq=Table[GraphData[{"Star",n},"MinimumCliqueCoveringCount"],{n,25}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"Star",n},"MinimumConnectedDominatingSetCount"],{n,25}]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"Star",n},"MinimumDistinguishingLabelingCount"],{n,25}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

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

Table[Piecewise[{{n,n==1||n==2}},(n-1) Gamma[n]],{n,25}]

%==seq

MinimumDominatingSetCount

seq=Table[GraphData[{"Star",n},"MinimumDominatingSetCount"],{n,25}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"Star",n},"MinimumEdgeCoverCount"],{n,25}]

MinimumVertexDegree

seq=Table[GraphData[{"Star",n},"MinimumVertexDegree"],{n,25}]

MolecularTopologicalIndex

seq=Table[GraphData[{"Star",n},"MolecularTopologicalIndex"],{n,25}]

FindSequenceFunction[seq,n]

Nonhamiltonian

Table[GraphData[{"Star",n},"Nonhamiltonian"],{n,25}]

OddChordlessCycleCount

seq=Table[GraphData[{"Star",n},"OddChordlessCycleCount"],{n,25}]

PathCount

seq=Table[GraphData[{"Star",n},"PathCount"],{n,25}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

Binomial[n,2]

PathPolynomial

(poly=Factor[Table[GraphData[{"Star",n},"PathPolynomial"],{n,k0=1,kmax=25}]/.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",{"Star",n}]["Pell"]

seq=Table[GraphData[{"Star",n},"Pell"],{n,25}]

PentagonCount

seq=Table[GraphData[{"Star",n},"PentagonCount"],{n,25}]

Perfect

Table[GraphData[{"Star",n},"Perfect"],{n,25}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"Star",n},"ProjectivePlaneCrossingNumber"],{n,25}]

Radius

seq=Table[GraphData[{"Star",n},"Radius"],{n,25}]

RectilinearCrossingNumber

seq=Table[GraphData[{"Star",n},"RectilinearCrossingNumber"],{n,25}]

Skewness

seq=Table[GraphData[{"Star",n},"Skewness"],{n,25}]

SpanningTreeCount

seq=Table[GraphData[{"Star",n},"SpanningTreeCount"],{n,25}]

SquareCount

seq=Table[GraphData[{"Star",n},"SquareCount"],{n,25}]

StabilityIndex

seq=Table[GraphData[{"Star",n},"StabilityIndex"],{n,25}]

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

TopologicalIndex

seq=Table[GraphData[{"Star",n},"TopologicalIndex"],{n,25}]

FindSequenceFunction[seq,n]//FullSimplify

ToroidalCrossingNumber

seq=Table[GraphData[{"Star",n},"ToroidalCrossingNumber"],{n,25}]

Traceable

Table[GraphData[{"Star",n},"Traceable"],{n,25}]

TriangleCount

seq=Table[GraphData[{"Star",n},"TriangleCount"],{n,25}]

TuttePolynomial

(poly=Factor[Table[GraphData[{"Star",n},"TuttePolynomial"],{n,k0=1,kmax=25}]/.f_Function:>f[x,y]])

Untraceable

Table[GraphData[{"Star",n},"Untraceable"],{n,25}]

VertexConnectivity

Table[GraphData[{"Star",n},"VertexConnectivity"],{n,25}]

VertexCoverNumber

Related to but not the same as IndependenceNumber

seq=Table[GraphData[{"Star",n},"VertexCoverNumber"],{n,25}]

VertexCount

seq=Table[GraphData[{"Star",n},"VertexCount"],{n,25}]

FindSequenceFunction[seq,n]

VertexDegrees

seq=Table[GraphData[{"Star",n},"VertexDegrees"],{n,25}]

Table[Append[ConstantArray[1,n-1],n-1],{n,25}]

WienerIndex

seq=Table[GraphData[{"Star",n},"WienerIndex"],{n,25}]

FindSequenceFunction[seq,n]

WienerSumIndex

seq=Table[GraphData[{"Star",n},"WienerSumIndex"],{n,25}]

FindSequenceFunction[seq,n]

GraphData

GraphDataString

file=OpenWrite["~/star.m"]

Do[WriteString[file,GraphDataString[StarGraph[n],
"StandardName"->{"Star",n},
"AlternateStandardNames"->{{"CompleteBipartite",{1,n-1}}},
"Name"->IntegerString[n]<>"\[Hyphen]star graph",
"AlternateNames"->{"(1,"<>IntegerString[n-1]<>")\[Hyphen]complete bipartite graph"},
"Classes"->{"CompleteBipartite","Star"},
"NotationRules"->{"CompleteBipartite"->{1,n-1},"Star"->n},
"Information"->"StarGraph",
TimeConstraint->10,
Debug->True
]],{n,21,25}]

Close[file]