Questions tagged [nauty]
Questions about the program Nauty (No AUTomorphisms, Yes?) used for studying isomorphisms of graphs.
9
questions
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 ...
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.
<...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...