# Finding all non-isomorphic $C_5$-free connected planar graphs of order 11.

Let us say that a graph is $H$-free if it does not contain $H$ as a subgraph (whether induced or not). We denote $C_5$ as a cycle with 5 vertices. Then I would like to find all the $C_5$ free planar connected graphs of order 11. (I can't estimate the number of them, hope it's not too many.) I tried to write the following code.

def C5free(g):
test=not graphs.CycleGraph(5).is_subgraph(g,induced=False)
return test


First, to check that the code will be executed correctly, I tried to filter out the 6 vertex $C_5$ free connected planar graphs. But the following code does not seem to filter the desired ones very well. Because 179 is the total number.

g6a=[g for g in graphs.planar_graphs(6,minimum_connectivity=1) if C5free(g)==True];
len(g6a) #179
g6b=[g for g in graphs.planar_graphs(6,minimum_connectivity=1)];
len(g6b) #179


However, obviously the graph with 6 vertices below is not $C_5$-free.

g=Graph([(0,1),(1,2),(2,3),(3,4),(4,0),(0,5)])


In addition, among these graphs, there may be some graphs being isomorphic to each other. Because we can see from the sequence about conencted planar graphs from https://oeis.org/A003094/list. It tells us that 99 is the number of non-isomorphic connected planar graphs on 6 vertices.

edit retag close merge delete

Sort by » oldest newest most voted

You can have a look at the questions tagged graph_generationfor more details and explanations about the following, see https://ask.sagemath.org/questions/sc...

• being planar is a property that is stable when we remove some edges
• being $C_5$-free is a property that is stable when we remove some edges
• being connected is not stable when we remove some edges

Hence, we can first generate all planar and $C_5$-free graphs with the graphs generators (using the augment="edges" option), and then filter the connected ones (the cost is not expensive since we already selected few graphs):

sage: C5 = graphs.CycleGraph(5)
sage: good_graphs = [g for g in graphs(6, property=lambda G: G.is_planar() and not C5.is_subgraph(G,induced=False, up_to_isomorphism=True ), augment="edges") if g.is_connected()]

sage: len(good_graphs)
43

sage: for g in good_graphs:
....:     show(g)

more

Thank you. For generating planar graphs, maybe planatri (sage’s interface planar_graphs) is better. According to its help document (http://users.cecs.anu.edu.au/~bdm/pla...), when planar graphs are not 3-connected, it returns some graphs that may be isomorphic.

• Isomorphisms are defined with respect to the imbeddings, so in some cases outputs may be isomorphic as abstract graphs.

We feel frustrating to try to get the desired graphs that are not isomorphic.

( 2022-10-17 05:56:34 +0200 )edit
1

The library that is used by the graphs generator is nauty, which is supposed to return non-isomorphic graphs (as graphs, not as embedded graphs).

( 2022-10-17 09:34:54 +0200 )edit

It would be faster to start by limiting the number of edges to less than or equal to $3n-6$. (The number of edges of a planar graph with $n$ vertices is less than or equal to $3n-6$). Does the function graphs has a parameter to specify the range of number of edges. I only see it in the function nauty_geng.

( 2022-10-18 03:33:26 +0200 )edit

I guess this would be useless since the generation algorithm works by augment edges (see the doc of the corresponding option), hence graphs with more edges will not be explored.

That said, you can try to do some benchmarks (use timeit) to see if adding this condition on the number of edges (which is is stable when we remove some edges) to the property function helps the generation.

( 2022-10-21 23:06:51 +0200 )edit

By default .is_subgraph() takes into account vertex labels while searching for subgraph. Since labels do not matter in your case, you need to add parameter up_to_isomorphism=True when calling .is_subgraph().

more

1

I updated my answer, thanks !

( 2022-10-16 22:46:50 +0200 )edit

Thanks! The parameter up_to_isomorphism=True seems to be added in new version (9.7). The sage in My computer is 9.6. Is there an alternative?

( 2022-10-17 05:24:00 +0200 )edit

Run ?Graph.is_subgraph to see the options supported by your version.

( 2022-10-19 16:25:08 +0200 )edit