Given a graph G, enumerate all connected, vertex-induced subgraphs of G up to a given size limit.

A subgraph S of G induced by the vertices {v_i1, ..., v_im} of G consists of those vertices with ⟨v_ip, v_iq⟩ being an edge in S iff it is an edge in G.

G may be undirected or directed; in the latter case generate weakly connected subgraphs.

Note that a (sub-)graph must have at least one vertex although having zero edges (the empty graph) is just fine.

 

First enumerate all subgraphs containing the seed vertex v₀.

Next enumerate all subgraphs containing the seed vertex v₁ but not v₀.

Then enumerate all subgraphs containing the seed vertex v₂ but neither v₀ nor v₁,

and so on.

 

Given a seed, the process is recursive. At each stage a vertex that is a neighbour of the current subgraph, and that has not yet been considered, is eligible to be added to the subgraph.

An eligible vertex, v, may be added or not added to the subgraph; those are the two options for v and they are both explored recursively.

If v is added to the subgraph it may cause other vertices to become neighbours of the enlarged subgraph.

The process backtracks whenever the maximum size is reached or there are no eligible vertices to add.

The current subgraph is processed whenever a new vertex is added to it.

-- L. A.,  Fri. 5th, Wed. 10th Sept. 2014.

Also search for [enumerate subgraph] in the [Bib].