1
$\begingroup$

Is there a way to generate a list of all $m$ subgraphs $g_1,g_2,\dots,g_m$ of a graph $G$ which don't contain a specified graph isomorphic to the graph $H$?

For example, all subgraphs of the complete graph which don't contain a 3-path $\Pi_3$ (3 edges, 4 vertices, in a path).

I can see Subgraph[g,patt], which according to the documentation

gives the subgraph generated by the vertices and edges that match the pattern patt.

But what is the usage?

I can see IGraphM has IGSubisomorphicQ which can test for subgraph containment. So one would then simply need to list all subgraphs effectively. Is this done with the power set of the edges?

$\endgroup$

1 Answer 1

3
$\begingroup$

To generate all the subgraphs of the complete graph:

kgraph = CompleteGraph[4];
HighlightGraph[kgraph, #] & /@ (Graph[VertexList@#, #] & /@ 
   Subsets[EdgeList[kgraph]])

enter image description here

and so on.

Then, to test for the subgraph, having loaded IGraph, use

subgraph = PathGraph[{1, 2, 3, 4}];
graphs=Graph[VertexList@#, #] & /@ Subsets[EdgeList[kgraph]];
Transpose[{graphs, 
IGSubisomorphicQ[subgraph, #] & /@ graphs}]

part of the output of which is displayed here:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.