Questions about the program Nauty (No AUTomorphisms, Yes?) used for studying isomorphisms of graphs.

learn more… | top users | synonyms

0
votes
2answers
93 views

Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$. Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...
4
votes
2answers
172 views

Details of generation programs supplied with nauty

The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was ...
1
vote
1answer
145 views

Generating k-partite graphs

Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...
1
vote
1answer
246 views

An example of when nauty, on two different platforms, gives different canonical labels for the same input graph? [closed]

Let $G$ be a graph. I've heard that, if we use nauty to canonically label $G$ on two different platforms, it's possible to obtain distinct labels. However, I've never actually seen this occur. The ...
1
vote
1answer
203 views

Is there a canonical labelling package optimised for small graphs?

Recently, I've been looking into motifs in networks (directed graphs) -- small connected induced subgraphs that appear significantly more frequently than in a "similar random graph". In practice, we ...