Table of Contents

Checking and generating $(r,c)$-graphs

We outline below a number of different utilities developed to check for $(r,c)$-graphs as well as to generate them.

---

Using for Mathematica to check for $(r,c)$-graphs

The following snippet returns `true' if a Graph instance G is an $(r,c)$-constant graph, and `false' otherwise.

constantGraphQ[G_] := Length[#] == 1 && #[[1]] >= VertexDegree[G, VertexList[G][[1]]] &[DeleteDuplicates[Table[EdgeCount[NeighborhoodGraph[G, v]], {v, VertexList[G]}]]];
        

Copy Code

Moreover, the following snippet returns `true' if a Graph instance G has a constant-link, and `false' otherwise.

hasConstantLinkQ[G_] := AllTrue[Table[NeighborhoodGraph[G, v], {v, VertexList[G]}], IsomorphicGraphQ[NeighborhoodGraph[G, VertexList[G][[1]]], #] &];
        

Copy Code

Many large instances in the database were found from the GraphData repository [5]. The following snippet returns all such graphs in the repository.

constantGraphs = Table[{GraphData[g[[2]]], g[[2]]}, {g, Select[ParallelTable[{constantGraphQ[GraphData[g]], g}, {g, GraphData[{"Regular", "Connected"}]}], #[[1]] &]}];
        

Copy Code

---

Using geng to generate $(r,c)$-graphs

In geng [6], graphs of a given order $n$ are constructed by adding vertices one by one. A graph generated at some intermediate step has the property that it is a vertex-induced subgraph of any graph generated subsequently.

Suppose that at some intermediate step the graph constructed has some vertex with degree greater than $r$ or an open neighbourhood with more than $c$ edges. Then clearly continuing to add vertices to this graph will not result in an $(r,c)$-graph on $n$ vertices, and therefore we can `prune' the search space by not considering this candidate graph any further.

We achieve this by making use of the PRUNE and PREPRUNE preprocessor variables for geng, in order to define appropriate functions which do such pruning. A number of other considerations are also made in order to find $(r,c)$-graphs effectively.

We would like to thank Brendan McKay for a number of insightful remarks into geng and also plantri [7].

Compilation and usage

The code below implements the PRUNE and PREPRUNE functions which restrict the search of geng to $(r,c)$-graphs.

#include "gtools.h"

long r, c;

int PREPRUNE(graph *g, int n, int maxn) {
    int i, j, k, v, e, nsub;
    setword *gv, *wgi;

    DYNALLSTAT(boolean,perm,perm_sz);
    DYNALLOC1(int,perm,perm_sz,n,"nbrhoodg");

    for (v = 0, gv = GRAPHROW(g,0,1); v < n; ++v, gv += 1) {
        if (ISELEMENT(gv, n - 1) || v == n - 1) {
            nsub = e = 0;

            for (i = 0; i < n; ++i) {
                if (ISELEMENT(gv, i) && i != v) perm[nsub++] = i;
            }

            for (i = 0; i < nsub; ++i) {
                wgi = GRAPHROW(g, perm[i], 1);
                for (j = 0; j < nsub; ++j) {
                    k = perm[j];
                    if (ISELEMENT(wgi,k)) e++;
                }
            }

            if (e > 2*c || nsub == r && e < 2*c || nsub > r) {
                DYNFREE(perm, perm_sz);
                return -1;
            }
        }
    }

    DYNFREE(perm, perm_sz);

    return 0;
}

int PRUNE(graph *g, int n, int maxn) {
    int i, j, k, v, e, nsub;
    setword *gv, *wgi;

    DYNALLSTAT(boolean,perm,perm_sz);
    DYNALLOC1(int,perm,perm_sz,n,"nbrhoodg");

    for (v = 0, gv = GRAPHROW(g,0,1); v < n; ++v, gv += 1) {
        nsub = e = 0;

        for (i = 0; i < n; ++i) {
            if (ISELEMENT(gv, i) && i != v) perm[nsub++] = i;
        }

        for (i = 0; i < nsub; ++i) {
            wgi = GRAPHROW(g, perm[i], 1);
            for (j = 0; j < nsub; ++j) {
                k = perm[j];
                if (ISELEMENT(wgi,k)) e++;
            }
        }

        if (e > 2*c || nsub == r && e < 2*c || (2*c - e) > 2*(r-1)*(maxn - n)) {
            DYNFREE(perm, perm_sz);
            return -1;
        }
    }

    DYNFREE(perm, perm_sz);

    return 0;
}

int GENG_MAIN(int argc, char *argv[]);

int main(int argc, char *argv[]) {
    if (argc < 4) exit(1);

    int geng_argc;
    char nstring[6]; /* String to put n into */
    char dstring[6];  /* String to put d into */
    char Dstring[6];  /* String to put D into */
    char *geng_argv[7]; /* At least one bigger than geng_argc */

    /* Read values for r and c */
    r = strtol(argv[1], NULL, 10);
    c = strtol(argv[2], NULL, 10);

    /* Set up geng argument list. */
    sprintf(nstring,"%s", argv[3]);
    sprintf(dstring,"-d%s", argv[1]);
    sprintf(Dstring,"-D%s", argv[1]);
    geng_argv[0] = "geng";
    geng_argv[1] = "-q";
    geng_argv[2] = "-c";
    geng_argv[3] = dstring;
    geng_argv[4] = Dstring;
    geng_argv[5] = nstring;
    geng_argv[6] = NULL;
    geng_argc = 6;

    GENG_MAIN(geng_argc,geng_argv); /* Pass arguments to geng */

    exit(0);
}

Copy Code

A CMAKE file is also included below to aid with linking and compiling. Ensure that the nauty source files are located at /usr/local/ for linking.

cmake_minimum_required(VERSION 3.23)
project(geng_rc_graphs C)

set(CMAKE_C_STANDARD 99)

set(NAUTY /usr/local/nauty)
include_directories(include ${NAUTY})

add_executable(${PROJECT_NAME} main.c ${NAUTY}/geng.c ${NAUTY}/gtools.h)
target_link_libraries(${PROJECT_NAME} ${NAUTY}/nauty.a)

set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -Ofast -DNDEBUG -DMAXN=WORDSIZE -DGENG_MAIN=geng_main -DPREPRUNE=PREPRUNE -DPRUNE=PRUNE")

Copy Code

---