List all connected subgraphs with exactly k vertices

asked 2023-06-28 10:23:35 +0100

licheng gravatar image

updated 2023-06-28 11:28:21 +0100

I love connected_subgraph_iterator, but it always lists all connected subgraphs or those with at most $k$ vertices .

What if I only want to obtain connected subgraphs with exactly $k$ vertices? We can, of course, produce connected subgraphs with no more than $k$ vertices and then pick them, but when $k$ is close to the odder of the input graph, It appears that there is room for improvement. 

# Example usage
G = graphs.CubeGraph(5) #order of G is 32
k=30
s=[g for g in G.connected_subgraph_iterator() if g.order()==k]

In Sage, must the generation of kth-order subgraphs rely on (k-1)-th or even smaller-order subgraphs?

edit retag flag offensive close merge delete

Comments

1

I'd assume that the following call should do the job but somehow it does not:

graphs(k, property=lambda H: H.is_connected() and H.is_subgraph(G, induced=False, up_to_isomorphism=True), augment='vertices')
Max Alekseyev gravatar imageMax Alekseyev ( 2023-06-29 03:18:00 +0100 )edit
1

It's not obvious to modify the current code of connected_subgraph_iterator to return graphs with exactly k vertices. More precisely, it's not obvious when returning non-induced subgraphs, but it's easy when we have vertices_only == True or when induced == True.

David Coudert gravatar imageDavid Coudert ( 2023-06-29 12:09:45 +0100 )edit

I added this idea in the wishlist: issue 35857.

David Coudert gravatar imageDavid Coudert ( 2023-06-29 16:08:13 +0100 )edit

@david - do you see what's wrong with the graphs(...) call I proposed above? I do not understand why it does not work.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-06-29 16:46:54 +0100 )edit
1

According the documentation of graphs, when parameter augment='vertices' all graphs up ton=vertices are generated.

sage: [g.order() for g in graphs(4)]
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
sage: [g.order() for g in graphs(4, augment='vertices')]
[0, 1, 2, 3, 4, 4, 4, 4, 3, 4, 4, 4, 4, 3, 4, 4, 2, 3, 4]
David Coudert gravatar imageDavid Coudert ( 2023-07-01 12:11:51 +0100 )edit
see more comments