Questions tagged [nauty]

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

7 questions
Filter by
Sorted by
Tagged with
69 views

nauty/traces orbit sizes for colored graph?

I'm given a graph $G$ (<1000 vertices, large automorphism group), and a large number (~10^6-10^10) of different colorings of said graph. I have two tasks. Calculate the canonical coloring. I can ...
• 91
309 views

Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
• 73
327 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 ...
267 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 ...
• 43
1 vote
196 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 ...
• 11
1 vote
303 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 ...
• 4,053
1 vote