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.

  • $\begingroup$ 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. $\endgroup$
    – eins6180
    Dec 11 '18 at 20:43
  • $\begingroup$ @eins6180 doesn't this potentially take an incredibly long time to find all isomorphic representations of g in $G$? $\endgroup$
    – Eric J
    Dec 11 '18 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.