Ask Your Question
1

How to check if a graph has a given subgraph?

asked 2021-03-12 16:10:53 +0100

Captcha gravatar image

updated 2021-03-12 16:51:22 +0100

slelievre gravatar image

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?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
3

answered 2021-03-12 16:41:07 +0100

slelievre gravatar image

updated 2021-03-13 14:25:32 +0100

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)
False

Up 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 vertices

See 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.

edit flag offensive delete link more

Comments

Thank you very much for such a detailed answer. Is there any method to find all the induced subgraphs isomorphic to H?

Captcha gravatar imageCaptcha ( 2021-03-13 03:29:01 +0100 )edit

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]
David Coudert gravatar imageDavid Coudert ( 2021-03-13 11:07:59 +0100 )edit

@Captcha it seems you tried to accept the answer but clicked twice, so that the answer was un-accepted.

slelievre gravatar imageslelievre ( 2021-03-13 15:39:13 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-03-12 16:10:53 +0100

Seen: 1,179 times

Last updated: Mar 13 '21