[Nauty] select C5-free graphs
Brendan McKay
Brendan.McKay at anu.edu.au
Wed Oct 4 00:07:21 AEDT 2023
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
More information about the Nauty
mailing list