Vertex-Induced Subgraph

Author

Eric W. Weisstein
April 5, 2020

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Vertex-InducedSubgraph.nb.

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

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

Example

Built-in

GraphicsRow[{g=CompleteGraph[10,VertexLabels->"Name"],Subgraph[g,{1,2,3,5,7,10},VertexLabels->"Name"]}]//StyleGraphs

MySubgraph

MySubgraph[g_System`Graph,v_,opts___?OptionQ]:=System`Graph[v,UndirectedEdge@@@Intersection[List@@@EdgeList[g],Subsets[v,{2}]],VertexCoordinates->GraphEmbedding[g][[v]],opts]

GraphicsRow[{g=CompleteGraph[10,VertexLabels->"Name"],MySubgraph[g,{1,2,3,5,7,10},VertexLabels->"Name"]}]//StyleGraphs

GraphicsRow[{g=PanGraph[8,VertexLabels->"Name"],MySubgraph[g,{2,3,4,5,9},VertexLabels->"Name"]}]//StyleGraphs

Combinatorica

{g=InduceSubgraph[CompleteGraph[10],r=RandomSubset[Range[10]]],r}

{g,r}={Graph[{{0,1,1,1,1,1},{1,0,1,1,1,1},{1,1,0,1,1,1},{1,1,1,0,1,1},{1,1,1,1,0,1},{1,1,1,1,1,0}},{{0.8090169943749475`,0.5877852522924731`},{0.3090169943749475`,0.9510565162951535`},{-0.30901699437494734`,0.9510565162951536`},{-1.`,0},{-0.3090169943749476`,-0.9510565162951535`},{1.`,0}}],{1,2,3,5,7,10}};

r

Show[GraphicsArray[{
showLabeledGraph[CompleteGraph[10],{},.15,PointSize[.04]],
showLabeledGraph[ChangeVertices[g,CircularVertices[10][[r]]],r,.15,PointSize[.04]]
}]]

Algorithms

$Version

gs=Graph[GraphData[#,"VertexList"],GraphData[#,"EdgeList"]]&/@GraphData["Connected",;;7];

Subgraphs[g_]:=Subgraph[g,#]&/@Subsets[VertexList[g]]

bug(391293): Speed up Subgraph

MaxMemoryUsed[sub1=Subgraphs/@gs]//Timing

mySubgraph[g_,v_]:=Block[{elist=List@@@EdgeList[g]},System`Graph[v,UndirectedEdge@@@Intersection[elist,Subsets[v,{2}]]]]
mySubgraphs[g_]:=mySubgraph[g,#]&/@Subsets[VertexList[g]]

MaxMemoryUsed[sub2=mySubgraphs/@gs]//Timing

Length[sub1]

Flatten[sub1]//Length

sub1===sub2

bug(391292): Subgraph returns graphs with edges that are not OrderedQ

sub1ordered=Take[sub1,All]/.g_Graph:>Graph[VertexList[g],Sort[EdgeList[g]]];//Timing

sub1ordered===sub2