[Nauty] select C5-free graphs

[Tomas Peitl]

Drop the -u to see the graphs.

Cheers,
Tomas

On 03.10.23 15:06, lczhangmath wrote:
> Dear Brendan,
>
>
> Thanks. But I cannot see these graphs. I just see the number (of C5 free graphs)
> How do I  change it. Do I miss something?
>
>
> Best wishes,
> Licheng
>
>
> ---- Replied Message ----
> | From | lczhangmath<lczhangmath at 163.com> |
> | Date | 10/03/2023 20:53 |
> | To | Brendan McKay<brendan.mckay at anu.edu.au>,
> nauty at anu.edu.au<nauty at anu.edu.au> |
> | Subject | Re: [Nauty] select C5-free graphs |
> Sorry. After I send my email, I see your new email.
>
>
> ---- Replied Message ----
> | From | lczhangmath<lczhangmath at 163.com> |
> | Date | 10/03/2023 20:51 |
> | To | Brendan McKay<brendan.mckay at anu.edu.au>,
> nauty at anu.edu.au<nauty at anu.edu.au> |
> | Subject | Re: [Nauty] select C5-free graphs |
> 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
> _______________________________________________
> 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