[Nauty] obtain all butterfly-free connected graphs with 16 vertices and 18 edges.
Brendan McKay
Brendan.McKay at anu.edu.au
Mon Apr 8 11:20:55 AEST 2024
The same PRUNE feature of geng (see the description in geng.c) can be used
for forbidden subgraphs, forbidden induced subgraphs, or many other
properties.
It is most efficient for properties that are uniform (removing a vertex
from a
graph with the property gives a smaller graph with the property).
The catch is that you have to write the code to test for your property.
In testing a
graph with vertices 0..n-1, you can assume that the subgraph with
vertices 0..n-2
already passed the test.
Brendan.
On 8/4/2024 12:53 am, lczhangmath via Nauty wrote:
> 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
More information about the Nauty
mailing list