Local Graph

Author

Eric W. Weisstein
June 9, 2009

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

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

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

Checks

g=Graph[{"Kneser",{7,2}}];

InduceSubgraph[g,Rest[Neighborhood[g,1,1]]]//RecognizeGraph

Neighborhood[Graph[{"Kneser",{7,2}}],1,1]

NeighborhoodVertices[Graph[{"Kneser",{7,2}}],1,1]

NeighborhoodVertices[Graph[{"Kneser",{7,2}}],1]

Enumeration

Length[l=Monitor[Select[GraphData["Connected"],TimeConstrained[LocalGraphQ[Graph[g=#]],5]&],g]]//Timing

gs=Monitor[{g=#,RecognizeGraph[LocalGraph[Graph[g]]]}&/@l,g]

Grid[Map[GraphData[#,"Name"]&,DeleteCases[gs,{_,{}|{"Empty"|"Path"|"LadderRung",_}|{_Integer,_Integer}}|{{"Circulant"|"Sextic"|"QuarticTransitive"|"UnitDistance"|"VertexTransitive",_},_}],{2}],Dividers->All,Alignment->Left]//TraditionalForm

ll=DeleteCases[{#[[1,1]],#[[All,2]]}&/@SplitBy[
Sort[Reverse/@gs],First],{{}|{"Empty",_},_}]

Grid[Sort[Function[f,{GetGraphData[f[[1]],"Name"],GetGraphData[#,"Name"]&/@f[[2]]}]/@Take[ll,All]],Dividers->All,Alignment->Left]//TraditionalForm