Questions tagged [nauty]

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

Filter by
Sorted by
Tagged with
4 votes
1 answer
445 views

Is there an algorithm to generate graphs with given order and diameter?

I saw a question on the nauty emailing list without receiving any response, and it's something I've encountered in my own research as well. I am currently interested in graphs with diameter 3. I ...
L.C. Zhang's user avatar
  • 1,605
4 votes
0 answers
201 views

How many 20-vertex 2-connected 5-regular non-Hamiltonian graphs are there?

As for the question in title, I attempted to use nauty to obtain them, but it has been running on my computer for nearly three days without producing any results. <...
L.C. Zhang's user avatar
  • 1,605
0 votes
0 answers
87 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 ...
J Bausch's user avatar
4 votes
0 answers
344 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 ...
Mathias's user avatar
  • 73
0 votes
2 answers
361 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 ...
Dominik Sieber's user avatar
5 votes
1 answer
346 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 ...
bart_m8's user avatar
  • 53
2 votes
1 answer
226 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 ...
caw's user avatar
  • 21
2 votes
1 answer
310 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 ...
Douglas S. Stones's user avatar
1 vote
1 answer
291 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 ...
Douglas S. Stones's user avatar