[Nauty] select C5-free graphs

[Brendan McKay]

Note that nopentagons is a spin-off of geng and has all the same switches.
It just has the additional feature of not allowing pentagons.

Generate all the 16-vertex graphs of girth at least 6:
    nopentagons -u -ft 16
683392 graphs generated in 7.79 sec

2-connected 19-vertex graphs of girth at least 6 and maximum
degree at most 3:
    nopentagons -u -ftD3 -C 19
272749 graphs generated in 25.89 sec

B/

On 3/10/2023 11:53 pm, lczhangmath wrote:
> Sorry. After I send my email, I see your new email.
>
> ---- Replied Message ----
> From 	lczhangmath<lczhangmath at 163.com> <mailto:lczhangmath at 163.com>
> Date 	10/03/2023 20:51
> 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
>
> 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> 
> <mailto:brendan.mckay at anu.edu.au>
> Date 	10/03/2023 20:13
> To 	nauty<nauty at anu.edu.au> <mailto: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