[Nauty] obtain all butterfly-free connected graphs with 16 vertices and 18 edges.

[lczhangmath]

Dear Prof. Brendan,
I reviewed the code for generating 4-hole free graph below and also consulted the nauty2.8.8 manual on page 80. Here are two links related to similar issues, which cover the C5_free graph I once inquired about.


https://mailman.anu.edu.au/pipermail/nauty/2002-November/000028.html （induced subgraph free)
https://mailman.anu.edu.au/pipermail/nauty/2023-October/000931.html （ subgraph free)
You seems to use the nice PRUNE facility,


However, I didn't understand how to write code in nauty to determine if a graph is H-free. Indeed, the property of being H-free is hereditary since a graph with n vertices is H-free, then so is H-v. It seems I need to learn more.


Is there a guide somewhat like the one for C5_free, for determining if a graph is H-free. 


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;
}
My plan is to input a graph's adjacency list or adjacency matrix, which would make modifications quite convenient. Moreover, I might need to set several forbidden subgraphs.


Best licheng
Licheng



















在 2024-04-08 09:23:56，"Brendan McKay via Nauty" <nauty at anu.edu.au> 写道：
>Once you incorporate a property filter into geng using the PRUNE facility,
>all the other options of geng, including number of edges, remain available.
>
>Brendan.
>
>On 8/4/2024 12:58 am, lczhangmath via Nauty wrote:
>> Of course, I'm also interested in more general modification schemes.  That is to say, obtain all butterfly-free connected graphs with n vertices and m edges.
>>
>>
>> Best wishes
>> Licheng
>>
>>
>>
>>
>> 在 2024-04-07 22:53:55，"lczhangmath" <lczhangmath at 163.com> 写道：
>>
>> Hi
>> The butterfly or bowtie graph is obtained by joining two copies of C3 at a common vertex. A butterfly-free graph is a graph that does not contain butterfly as a subgraph.
>>
>>
>> I would like to obtain all   butterfly-free connected graphs with 16 vertices and 18 edges.
>>
>>
>> I understand that, with certain modifications, geng can be utilized to produce programs that exclude specific subgraphs or induced subgraphs. Guenter Stertenbrink mentioned that his old program was capable of obtaining induced-subgraph-free graphs.
>>
>>
>> I'm now interested in generating subgraph-free graphs, rather than induced subgraph-free graphs. How to do.
>> Best
>> Licheng
>> _______________________________________________
>> 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