[Nauty] select C5-free graphs

[Brendan McKay]

Take off -u.  It means "just count" in many of my programs.   B/

On 4/10/2023 12:06 am, 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> <mailto:lczhangmath at 163.com>
> Date 	10/03/2023 20:53
> To 	Brendan McKay<brendan.mckay at anu.edu.au> 
> <mailto:brendan.mckay at anu.edu.au>,
> nauty at anu.edu.au<nauty at anu.edu.au> <mailto: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