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

Finding all non-isomorphic

$C_5$ -free connected planar graphs of order 11.

licheng
311 ●6 ●25 ●43

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)])

image description

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.

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2 years ago

tmonteil
27473 ●32 ●205 ●519 http://wiki.sagemath.o...

updated 2 years ago

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)

link

Comments

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.

licheng ( 2 years ago )

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).

tmonteil ( 2 years ago )

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.

licheng ( 2 years ago )

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.

tmonteil ( 2 years ago )

add a comment

answered 2 years ago

Max Alekseyev

6892 ●9 ●51 ●160

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().

link

Comments

I updated my answer, thanks !

tmonteil ( 2 years ago )

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?

licheng ( 2 years ago )

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

Max Alekseyev ( 2 years ago )

add a comment

Your Answer

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

Add Answer

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

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Finding all non-isomorphic C5C_5-free connected planar graphs of order 11. savecancel

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

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