[Nauty] select C5-free graphs

[lczhangmath]

Dear Prof. Brendan,


Thank you for telling me the new option -P. Indeed, for C5 free graphs, it may need change something in the function  numpentagons() to improve its picking speed. 


And you say: "nopentagons -u 11" finds all the 
11-point graphs without pentagons. Where is nopentagons? Is it a new generator? 


Best wishes,
Licheng.


---- Replied Message ----
| From | Brendan McKay<brendan.mckay at anu.edu.au> |
| Date | 10/03/2023 20:13 |
| To | nauty<nauty at anu.edu.au> |
| Subject | Re: [Nauty] select C5-free graphs |
The version of copyg and pickg in 2.8.7 (prerelease) has an option -P
for counting pentagons.  It is a bit of waste to count all of them if you
are going to reject everything with at least 1, but that's the situation
right now.  The function numpentagons() in gutil1.c count be copied
and converted into a test that returns when it finds the first pentagon.

If what you are after is to generate small graphs without pentagons, it
is much more efficient to use a pruning function in geng.  For example,
generating all the graphs with 11 vertices takes seconds and counting
their pentagons takes seconds.  But "nopentagons -u 11" finds all the
11-point graphs without pentagons in 1.6 seconds (there are 95428).
Even this is not the fastest method as it could be built into geng in
the same way that -t avoids 3-cycles and -f avoids 4-cycles. It has
been on my list of things to do for a long time.






On 2/10/2023 5:22 pm, lczhangmath wrote:
> Hello everyone,
>
>
> I would like to know if nauty offers an option to select C5-free graphs. (whether induced or not). Although I know it includes C3-free and C4-free options (-T0 and -W0).  Using some external scripts, for example Python can also do it, or use SageMath:
>
>
> sage: C5 = graphs.CycleGraph(5)
> sage: good_graphs = [g for g in graphs(6, property=lambda G: not C5.is_subgraph(G,induced=False, up_to_isomorphism=True ), augment="edges") if g.is_connected()]
>
>
> But how should I write the C version? I would like to learn how nauty filters graphs. Of course, I prefer more general options such as subgraph-free (or induced subgraph-free), although they are NP-hard in terms of algorithms.
>
>
>
>
> Best wishes.
> Licheng Zhang
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty

_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
https://mailman.anu.edu.au/mailman/listinfo/nauty