[Nauty] Questions - Generating graph families

[Brendan McKay]

Hi Diego,

The tools for doing exactly this are not present, but it is a suitable 
candidate
for the PRUNE/DEGPRUNE feature of geng.c because the property is inherited
by induced subgraphs.

Make a file diego.c like this:
-------------------------------------------------------

#include "gtools.h"

boolean diego(graph *g, int n, int maxn)
/* Return TRUE if it can be determined that every descendant
    will have 3 or more vertices of degree >= 3. */
{
     int i,numbig;

     if (POPCOUNT(g[n-1]) < 3) return FALSE;

     numbig = maxn - n + 1;
     if (numbig > 2) return TRUE;

     for (i = n-1; --i >= 0; )
     {
         if (POPCOUNT(g[i]) > 2) ++numbig;
         if (numbig > 2) return TRUE;
     }

     return FALSE;
}

-------------------------------------------------------

Now compile like this:

gcc -o diego -O3 -march=native -DMAXN=WORDSIZE -DWORDSIZE=32 -DPREPRUNE=diego geng.c diego.c nautyW1.a

The program diego now has all the features of geng except that the 
output is restricted to those graphs with at most two vertices of degree 
 > 2.

The idea with a pruning function is that returning TRUE causes this 
graph and all its descendants to be discarded.  This example uses the 
fact that the latest vertex added (vertex n-1 here) is a vertex of 
maximum degree in this subgraph.  (This does NOT imply that the vertices 
are in non-decreasing order of degree.)

For example, "diego 18" makes 1500591 graphs in 110 seconds, and "diego 
-c 18" makes 281579 connected graphs in the same time.  My tests were 
very brief so use with care.

These graphs have a rather simple structure and making them directly 
would be much faster, at the cost of more complicated programming.

Brendan.

On 15/7/2023 9:30 am, Diego J wrote:
> *Good morning,*
>
> I am using nauty and traces software to generate families of graphs. I need
> to generate a family with maximum of 2 vertices of degree greater than or
> equal to 3, which I don't know if it's possible. I would like everyone's
> help.
>
> Diego.
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty