Spider Graph

Author

Eric W. Weisstein
May 16, 2017

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

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

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

Plots

New

GraphicsGrid[DeleteCases[Table[Select[Trees[n],SpiderGraphQ]/.g_System`Graph:>SetProperty[g,{VertexSize->{"Scaled",.1},System`VertexStyle->Red,System`EdgeStyle->Black}],{n,8}],{}],ImageSize->500,Spacings->80]

Old

GraphicsGrid[Map[GraphPlot,DeleteCases[Table[Select[Trees[n],SpiderQ[#,True]&],{n,8}],{}],
{2}],ImageSize->500]

Enumeration

A004250

Table[Total[Boole[SpiderGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Total[Boole[SpiderGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Table[Total[Boole[SpiderGraphQ/@Trees[n]]],{n,16}]//Timing

Table[Length@GraphData["Spider",n],{n,12}]

Using Degree sequences

{#,RealizeDegreeSequence[#]}&/@Select[Partitions[6],Length[#]≥3&]//Column

Formulas

P(n-1)-(Floor[((n+1)/2)])

Table[PartitionsP[n-1]-Floor[(n+1)/2],{n,20}]

Explicit Partitions selection

Length/@Table[Select[Partitions[n-1],Length[#]≥3&],{n,20}]

Table[Count[Length/@Partitions[n-1],_?(#>2&)],{n,20}]

Table[Count[Length/@Partitions[n-1],_?(GreaterThan[2])],{n,20}]

Table[Total[Boole[GreaterThan[2]/@Length/@Partitions[n-1]]],{n,20}]

Length/@Table[IntegerPartitions[n-1,{3,n-1}],{n,20}]

Generating Function

Product[1-(q^k),{k,n+3}]

Sum[((q^n)/(QPochhammer[q,q,3+n])),{n,0,∞}]

Series[Sum[((q^(n+4))/(QPochhammer[q,q,n+3])),{n,0,50}],{q,0,20}]

Classes

Spiders are not necessarily Lobsters

Select[GraphData["Spider"],GraphData[#,"Lobster"]=!=True&]

(nls=Select[GetGraphData[All],MemberQ[c=GetGraphData[#,"Classes"],"Spider"]&&!MemberQ[c,"Lobster"]&])//Timing

Length/@SplitBy[Sort[{GetGraphData[#,"V"],#}&/@nls],First]

But not necessarily Caterpillars

Select[GraphData["Spider"],GraphData[#,"Caterpillar"]=!=True&]

Checks

SpiderQ[g_]:=TreeGraphQ[g]&&With[{d=Sort[VertexDegree[g]]},d[[-1]]≥3&&d[[-2]]≤2]

Sort[VertexDegree[GraphData["ButterflyGraph"]]]

DeleteCases[{GraphData[#,"Spider"],SpiderQ[GraphData[#]]}&/@GraphData[;;10],{x_,x_}]//Timing

GraphData

GraphClassString

GraphClassString[GraphData["Spider"]]