[Nauty] select C5-free graphs

[Brendan McKay]

I clicked "send" too soon.  I'll try again:

The version of copyg and pickg in 2.8.7 (prerelease) has an option -P
for counting pentagons.  It is a bit of a 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 could 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 392 seconds and counting
their pentagons takes 857 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.

Here is nopentagons.c.  Compile like this:

gcc -o nopentagons [optimization options] -DPRUNE=nopentagons 
nopentagons.c geng.c nauty.a

#include "gtools.h"

int
nopentagons(graph *g, int n, int maxn)
{
     int x,y;
     setword w,ax,ay;

     for (y = 1; y < n-1; ++y)
     {
         w = g[y] & ~BITMASK(y);
         while (w)
         {
             TAKEBIT(x,w);
             ax = (g[x] & g[n-1]) & ~bit[y];
             ay = (g[y] & g[n-1]) & ~bit[x];
             if (POPCOUNT(ax)*POPCOUNT(ay) > POPCOUNT(ax&ay)) return 1;
         }
     }

     return 0;
}


Brendan.


> 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
>