[Nauty-list] directed bipartite graphs using genbg and directg

Anastasia cryptovolans at gmail.com
Thu Jul 12 10:26:18 EST 2007


Hello All,
I have a limited understanding of graph theory, so I appreciate your
patience and any advice or corrections.

I am attempting to generate nonisomorphic, unlabeled, directed, bipartite
graphs. Both genbg and directg are working well, but I need a few more
graphs than directg returns. 

For example, I used ./genbg -c -d2:1 -D4:100 2 2 1:100 | ./directg -T, so
there are 2 vertices in the first set (0 and 1) and 2 vertices in the second
set (2 and 3).
One of the graphs output by directg is:
0 2 2 0 0 3 3 0 1 2 2 1 1 3
but it doesn't output this graph:
0 2 2 0 0 3 3 0 1 2 2 1 3 1

I think these graphs are nonisomorphic if they are considered as bipartite
(so I need both graphs), but are isomorphic if they are not considered as
bipartite (so the second graph is omitted by directg). Is it possible to get
these directed bipartite graphs with options/modifications in directg?

Thank you for your time,
Anastasia





More information about the Nauty mailing list