
 The 'subgraph isomorphism problem':
Given graphs G_{α} and G_{β},
does G_{β} contain a subgraph
that is isomorphic
to G_{α}?
 In other words, is there a 11 (into) mapping,
ρ : V_{α} → V_{β},
such that
∀ vertices u, v, in G_{α},
if u and v are adjacent in G_{α}
then vertices ρ(u) and ρ(v) are adjacent in G_{β}?
 There^{ }are variations on the problem:
 Decision problem (y/n): Is there any such isomorphism, or not?
 Enumeration problem: Enumerate all such isomorphisms, if any.
 We may be given directed graphs or undirected graphs.
 The 'vertex induced subgraphisomorphism problem':
Does G_{β} contain a vertex induced subgraph
that is isomorphic to G_{α}?
In other words, is there a 11 mapping,
ρ : V_{α} → V_{β},
such that
∀ vertices u, v, in G_{α},
vertices u and v are adjacent in G_{α} if and only if
ρ(u) and ρ(v) are adjacent in G_{β}?
 Subgraph^{ }isomorphism is an NPcomplete problem.
(For a fixed G_{α} the problem is polynomial
in G_{β} but the polynomial depends on G_{α}.)
The following assumes undirected graphs, symmetric matrices.
Sources
Search for [subgraph isomorphism]
in the [bib].

