I'm glad that Mathematica 13.2 has fixed the previous error. FindIsomorphicSubgraph[g1,g2,All] gives all the subgraphs of $g_1$ that are isomorphic to $g_2$. Take a look at the previous discussion.
Today's question is a bit different. Given two graphs $G$ and $H$, we want to find all induced subgraphs of $G$ that are isomorphic to graph $H$.
- A subgraph $G_1$ of $G_2$ is called induced, if for any two vertices $u$,$v$ in $G_1$, $u$ and $v$ are adjacent in $G_1$ if and only if they are adjacent in $G_2$.
For example,
g1 = Graph[ImportString["Gr`HW{", "Graph6"],
VertexLabels -> Automatic]
If we want to find the subgraphs of a graph that are isomorphic to $K_{1,3}$ (also commonly called a claw), we can execute the following code:
subg2 = CompleteGraph[{1, 3}]
allsub=FindIsomorphicSubgraph[g1, subg2, All]
However, if we want to find all induced subgraphs that are isomorphic to $K_{1,3}$, some of the above subgraphs do not meet the criteria. For example, the last subgraph is not an induced subgraph of g1 because vertices $6$ and $7$ are adjacent in g1 .
I thought of a relatively naive method, which is to filter out induced subgraphs from the aforementioned subgraphs. However, this method has drawbacks, because an extreme case is when there are many subgraphs in graph g that are isomorphic to subgraph $K_{1,3}$, but none of them are induced subgraphs. So, is there a better way to directly find these induced subgraphs without first generating all these subgraphs and then filtering them?
(* test if a graph h is an induced subgraph of g*)
InduceSubgraphQ[g_, h_] :=
SubsetQ[VertexList[g], VertexList[h]] &&
EdgeList[Subgraph[g, h]] == EdgeList[h];
Select[allsub, InduceSubgraphQ[g1, #] &]
It shows that there are only 4 induced graphs isomorphic to $K_{1,3}$.
