Ask Your Question
0

How to determine whether a graph has l cycles of length k exactly?

asked 2024-03-05 12:18:33 +0100

licheng gravatar image

updated 2024-03-06 04:16:51 +0100

Given integers$ l\ge 0$, $k\ge 3$, and a graph, I want to know if it contains $l$ $k$-cycles exactly. I could enumerate all cycles of length k using the link below and count them, but this might not be very efficient. - subgraph_search_iterator-gives-duplicate-subgraphs

G=graphs.OctahedralGraph()
H = graphs.CycleGraph(3)
print( sum(1 for _ in G.subgraph_search_iterator(H, induced=False,return_graphs=False) ) )
L = { tuple(g.edges(labels=False,sort_vertices=True,sort=True)) for g in G.subgraph_search_iterator(H, induced=False) }
print(len(L))

In an import case for me, determinie if a graph has a unique $k$-cycle (when $k=1$), I don't need to list all cycles and then check; instead, obtaining two cycles would suffice, and the algorithm stops.

Similarly, such questions can be asked about subgraphs

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2024-03-05 14:57:39 +0100

Max Alekseyev gravatar image

You can unroll the construction for L to an early break:

def l_kcycles(G,l,k):
    H = graphs.CycleGraph(k)
    L = set()
    for g in G.subgraph_search_iterator(H, induced=False):
        L.add( tuple(g.edges(labels=False,sort_vertices=True,sort=True)) )
        if len(L)>l:
            return False
    return len(L)==l
edit flag offensive delete link more

Comments

Thanks for the solution.

mia02 gravatar imagemia02 ( 2024-03-14 13:09:50 +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: 2024-03-05 12:18:33 +0100

Seen: 2,879 times

Last updated: Mar 06