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

[Brendan McKay]

I have only ever done it in an ad-hoc way for particular fixed H.

If you want code that will work for a more general H, that is the
subgraph isomorphism problem which is complicated. Probably
a simple backtrack search will be adequate for this application
because the graphs are small, but in the near future I have no
time to do it.

Brendan.

On 8/4/2024 1:30 pm, lczhangmath wrote:
> 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