### Subgraph Enumeration

- 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_{0}. - Next enumerate all subgraphs containing the
seed vertex v
_{1}but not v_{0}. - Then enumerate all subgraphs containing the
seed vertex v
_{2}but neither v_{0}nor v_{1}, - 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].