First time here? Check out the FAQ!

Ask Your Question
1

Create program to find which graphs contain specific subgraph

asked 5 years ago

merluza gravatar image

Hello, I am pretty new to Sage, and am discovering all the wonderful things it can do. I know how to ask Sage to generate a list of graphs that satisfy particular properties. To do this I "call" a program named "nauty". For example, if I would like to generate all graphs with 10 vertices, 25 edges, and clique number 4 I type the following:

sage: g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]

Now say that I want to check which of these graphs contain a particular subgraph. For example, say I want to know which one of these graphs contain a 5-cycle. How can I ask Sage to go through the list of graphs in g10 and tell me this information?

Thank you in advance!

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
1

answered 5 years ago

dazedANDconfused gravatar image

updated 5 years ago

How about:

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
    if g.subgraph_search(H,induced=False):
        g.show()

After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs. The documentation for subgraph_search is here.

EDIT: With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
    if g.subgraph_search(H,induced=False):
        for p in g.subgraph_search_iterator(K,induced=True):
            for v in p:
                if g.degree(v)<6:
                    print "False"
                    print p
                    g.show()
                else:
                    print "True"

For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.

Preview: (hide)
link

Comments

Thank you for your help. Would you also happen to know how I can ask Sage to give me graphs in g10 that also satisfy the condition that every vertex in a 4-clique has degree at least 6?

merluza gravatar imagemerluza ( 5 years ago )

Thank you!! You are a lifesaver! I was unaware of subgraph_search_iterator tool, this is wonderful.

merluza gravatar imagemerluza ( 5 years ago )

There is an extensive, almost 900 page, pdf reference doc just on graph theory which is available here.

dazedANDconfused gravatar imagedazedANDconfused ( 5 years ago )

Your Answer

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

Add Answer

Question Tools

2 followers

Stats

Asked: 5 years ago

Seen: 914 times

Last updated: Apr 01 '19