Question: Finding induced subgraph isomorphism needs to be implemented.

The (Induced) Subgraph Isomorphism computational problem is, given H and G, determine whether there is a (induced) subgraph isomorphism from H to G. See https://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem

In Maple, IsSubgraphIsomorphic(G1,G2)  returns true if G1 is isomorphic to some subgraph of G2. However, it does not provide options for induced subgraphs. For example, 

with(GraphTheory):
claw:=CompleteGraph(1,3);
g:=CompleteGraph(2,2,2,2):
DrawGraph(g);
IsSubgraphIsomorphic(claw,g) #true

So the graph g contains a claw as a subgraph. But every claw in graph g  is non-induced. So g does not contain any induced claw. Maple does not appear to have this feature to determine if a graph contains a induced subgraph isomorphic to another graph. It is unclear whether we can modify some code in IsSubgraphIsomorphic  to achieve this goal.

Please Wait...