[Nauty-list] generating unlabeled bipartite graphs

[Gunnar Brinkmann]

Brendan: Copy to the mailing list just because you or others might 
answer too. In case there were no other answers,
no need to distribute it I think.

-----------------------------------------------------------------------------------------------------------

Dear Abhishek,

You wrote

> Yes the groups are different and the graphs are still bipartite 
> graphs. But the number of unlabeled graphs is usually different. For 
> example, consider the case where each of the two partitions have 2 
> sets each, and each set has two vertices; i.e. 
> set1:=[1,2],set2:=[3,4],set3:=[5,6],set4:=[7,8], and 
> partition1:=Union(set1,set2), partition2:=Union(set3,set4). Given that 
> the vertices within a set are identical to each other and between two 
> sets are different, the number of unlabeled bipartite graphs (or the 
> number of orbits of the induced automorphism group on all the labeled 
> bipartite graphs) are 5488. This number is different from the number 
> of unlabeled bipartite graphs with partitions [1,2,3,4] and [5,6,7,8]. 
> This number is 317. The number of labeled bipartite graphs in both the 
> cases is the same - 65536.
>  
> So, basically in my problem the aut(G) is a subgroup of the usual 
> aut(G) for bipartite graphs. I don't know if this difference can be 
> taken care of by the existing code in genbg. Please reply back with 
> your thoughts on how I should handle the problem - more specifially - 
> do i need to implement the graph generation algorithm completely for 
> my problem?

So I guess I understood it correctly. But then it is a typical case for 
the homomorphism principle. That is: Instead of modifying
the genbg code yourself, which is -- as I already wrote -- a bad idea 
anyway, you can just START with the graphs being produced
by genbg and then just produce the ones you need FROM them. This can be 
done by piping the output of
genbg into another program or write a "plugin".

You can find an informal description and an example of what I mean in

G.~Brinkmann.  Isomorphism rejection in structure generation programs. 
DIMACS Series on Discrete Mathematics and Theoretical Computer Science 
51, Discrete Mathematical Chemistry, 25--38, 2000. Proceedings of the 
DIMACS Workshop on Discrete Mathematical Chemistry 1998.

Do you have access to it or should I send some PS-file, of it ?

Gunnar