[Nauty] Generate all non-isomorphic graphs without edges between the last k vertices
mskala at ansuz.sooke.bc.ca
mskala at ansuz.sooke.bc.ca
Fri Jun 14 00:30:33 AEST 2019
On Thu, 13 Jun 2019, Andy Mercer wrote:
> What do you mean by "no edges within the subset of vertices > k "? Do you
> want all non-isomorphic graphs on N vertices having at least k isolated nodes
> (at least k nodes of degree zero)?
An edge "within" a subset of vertices means an edge with both endpoints in
the subset. So my reading of the desired condition is that the vertices
with indices >k are not necessarily isolated vertices - they might have
edges to other vertices with indices at most k - but the subgraph
induced by the set of vertices with indices >k contains no edges.
I doubt that geng can do this all by itself. Depending on the scale of
the project (size of graphs, number of them, how often I wanted to do this
kind of generation) I'd be inclined to either write a filter program for
geng's output to pass only the desired graphs, or go all the way to
writing my own generator program; it wouldn't be hard to tweak the orderly
generation framework to do similar filtering on the fly.
--
Matthew Skala
mskala at ansuz.sooke.bc.ca People before tribes.
https://ansuz.sooke.bc.ca/
More information about the Nauty
mailing list