Consider the Petersen graph G.
I want to check if G has a given graph H as an induced subgraph or not.
Is it possible to check this? I am new to SageMath.
I wrote this:
G = graphs.PetersenGraph()
H = Graph({1: [2, 3, 4]})How to check if H is an induced subgraph of G or not?
One could use the is_subgraph method of H, with induced=True.
Or if the question is up to isomorphism, use the search_subgraph method of G.
Define the two graphs:
sage: G = graphs.PetersenGraph()
sage: H = Graph({1: [2, 3, 4]})Is the small one a subgraph:
sage: H.is_subgraph(G)
False
sage: H.is_subgraph(G, induced=True)
FalseUp to isomorphism:
sage: G.subgraph_search(H)
Subgraph of (Petersen graph): Graph on 4 vertices
sage: G.subgraph_search(H, induced=True)
Subgraph of (Petersen graph): Graph on 4 verticesSee the documentation of these methods and related methods:
sage: H.is_subgraph?
sage: G.subgraph_search?Related methods exist to
count the number of (induced or not) subgraphs of G isomorphic to H:
sage: G.subgraph_search_count?generate all (induced or not) subgraphs of G isomorphic to H:
sage: G.subgraph_search_iterator?See an example of usage in @David Coudert's comment.
Thank you very much for such a detailed answer. Is there any method to find all the induced subgraphs isomorphic to H?
as indicated in above answer, use G.subgraph_search_iterator(H, induced=True).
sage: L = list(G.subgraph_search_iterator(H, induced=True))
sage: len(L)
60
sage: L[0]
[0, 1, 4, 5]
sage: L[1]
[0, 1, 5, 4]Asked: 4 years ago
Seen: 1,387 times
Last updated: Mar 13 '21
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
