Ask Your Question
1

How can I count the number of cycles of special length in a graph in sage?

asked 2016-12-01 02:07:54 -0500

M95 gravatar image

updated 2017-01-08 05:02:18 -0500

FrédéricC gravatar image

I have tried the G.subgraph_search_count(graphs.CycleGraph(4))but it doesn't lead to the correct answer, any help would be appreciated.

edit retag flag offensive close merge delete

Comments

Would it suffice to divide by the size of the automorphism group of the subgraph that is being searched for, perhaps? In other words, are you trying to count non labelled occurrences of cycles? For the particular case stated in your question, dividing by 8 might do the trick.

fidbc gravatar imagefidbc ( 2016-12-02 10:00:46 -0500 )edit

Yes ,That's what I'm trying to do,but what is 8 that it should be divided by?

M95 gravatar imageM95 ( 2016-12-02 13:10:26 -0500 )edit

I meant you should divide by 8 if you are searching 4-cycles, since the size of the automorphism group of the 4-cycle is 8. See answer below for further details.

fidbc gravatar imagefidbc ( 2016-12-03 10:49:39 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2016-12-03 11:06:47 -0500

fidbc gravatar image

updated 2016-12-03 11:09:35 -0500

Seems like you are searching for non labelled occurrences of cycles. In such case dividing by the size of the automorphism group of the graph that is being searched for might do the trick. Say you are trying to count the number of unlabelled appearances of graph H in graph G. You can define

subgraph_count = lambda G,H: G.subgraph_search_cound(H)/H.automorphism_group(return_group=False,order=True)

and then use

G=graphs.Grid2dGraph(3,3)
H=graphs.CycleGraph(4)
subgraph_count(G,H)

This should output 4, as expected.

For the particular case of cycles, if you are searching for cycles of length k then it suffices to divide by 2*k, so the following should work.

cycle_subgraph_count = lambda G,k: G.subgraph_search_cound(graphs.CycleGraph(k))/(2*k)

then

G=graphs.Grid2dGraph(10,10)
cycle_subgraph_count(G,4)

should output 81.

edit flag offensive delete link more

Comments

Thank you so much,I got it.

M95 gravatar imageM95 ( 2016-12-03 12:32:40 -0500 )edit

You're welcome! If this worked for you, you can mark the answer as accepted ;-)

fidbc gravatar imagefidbc ( 2016-12-03 13:15:29 -0500 )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: 2016-12-01 02:07:54 -0500

Seen: 131 times

Last updated: Dec 03 '16