# Repeated subgraph isomorphism query for single-edge addition for bounded degree graphs

I have a source undirected colored graph $$G$$ and a base query graph $$g$$. I know $$g$$ is subisomorphic to $$G$$ and now I want to identify which edges I can add to $$g$$ to preserve subisomorphism. That is, for any pair of vertices $$(v_i, v_j)$$ in $$g$$ if $$g' = g \cup e_{i,j}$$ is $$g'$$ still subisomorphic to $$G$$? what I'm trying to find is the set of single-edges I could add to $$g$$ while retaining subisomorphism. If it helps my graph has bounded degree < 5, and there are always fewer than 100 nodes.

• Add an edge to $g$ and assume this extended graph is subisomorphic to $G$ via $\phi$. Then $\phi$ also shows that just $g$ itself is subisomorphic to $G$. This means it's enough to go through all isomorphic representations $h_1, \ldots, h_k$ of $g$ in $G$ and list all the edges between vertices of $h_i$ that are in $G$ but not in $h_i$ itself. Dec 11 '18 at 20:43
• @eins6180 doesn't this potentially take an incredibly long time to find all isomorphic representations of g in $G$? Dec 11 '18 at 23:08