Graph Expansion

Author

Eric W. Weisstein
November 3, 2008

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

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

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

Old Code

GraphExpansion[g_,{n_,step_}]:=Module[
{
l=Flatten[Position[Degrees[g],1]],
v=V[g],
i,k
},
AddEdges[GraphUnion[n,g],
Sort/@Flatten[Partition[#,2,1,1]&/@Table[Mod[v k step[[i]]+l[[i]]-1,v n]+1,{i,Length[l]},{k,0,n-1}],1]
]
]

GraphExpansionList[g_,{n_,step_}]:=Module[
{
l=Flatten[Position[Degrees[g],1]],
v=V[g],
i,k
},
Table[Mod[v(i-1)+k step[[i]]+l[[i]]-1,v n]+1,{k,0,n-1},{i,Length[l]}
]
]

Code

GraphExpansion[g_,{n_,step_}]:=Module[
{
l=Flatten[Position[Degrees[g],1]],
v=V[g],
i,k
},
AddEdges[GraphUnion[n,g],Flatten[Table[Mod[{l[[i]]+k v,l[[i]]+step[[i]]v+k v}-1,n v]+1,{i,Length[l]},{k,0,n-1}],1]]
]

Examples

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{4,{1,1}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{5,{1,2}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{8,{1,3}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{10,{1,2}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{10,{1,3}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{12,{1,5}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["K2"],{24,{1,5}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["Claw"],{14,{1,3,5}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["Claw"],{28,{1,3,9}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["Claw"],{56,{1,9,25}}]],V[g]}

{RecognizeGraph[g=GraphExpansion[Graph["HGraph"],{17,{1,2,4,8}}]],V[g]}

Select[Subsets[Range[8],{4}],SymmetricGraphQ[GraphExpansion[Graph["HGraph"],{17,#}]]&]

{RecognizeGraph[g=GraphExpansion[Graph["HGraph"],{17,{3,5,6,7}}]],V[g]}

GraphData["BiggsSmithGraph","StandardNames"]

{RecognizeGraph[g=GraphExpansion[Graph["HGraph"],{34,{1,9,13,15}}]],V[g]}

Select[Subsets[Range[15],{4}],SymmetricGraphQ[GraphExpansion[Graph["HGraph"],{34,#}]]&]

{RecognizeGraph[g=GraphExpansion[Graph["HGraph"],{34,{3,5,7,11}}]],V[g]}

Embeddings

GraphExpansion[Graph["K2"],{4,{1,1}}]//GraphPlot

GraphExpansion[Graph["K2"],{5,{1,2}}]//GraphPlot