[Nauty-list] generating unlabeled bipartite graphs

[Abhishek]

Hi,

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?

Thanks and Regards,
Abhishek


On 8/18/06, Gunnar Brinkmann <Gunnar.Brinkmann at ugent.be> wrote:
>
> Dear Abhishek,
>
> You wrote
>
> > I am trying to generate bipartite graphs where each vertex partition
> > is a collection of sets. Two vertices in the same set are identical to
> > each other, but two vertices in different sets are different. If each
> > of the partitions were made of only set then I could have used genbg
> > to generate the unlabeled graphs. But in my case the automorphism
> > group of the bipartite graph is different from the usual case (since
> > every vertex in a partition may not be identical to every other vertex
> > in the same partition). What I want to know is that is there a way to
> > generate such graphs by modifying some portion of the genbg code? If
> > yes, what portions?
> > I would appreciate any help in this regard. I have myself spent quite
> > some time on the code and have found it quite difficult to understand
> > it well enough to answer my question.
> >
>
> I think that you shouldn't modify the genbg code anyway. It is always
> very dangerous to modify other peoples codes...
> I sometimes do so for testing purposes, but never more.
>
> But I don't see why you can't use genbg. I do see that the groups are
> different, but the graphs are not. Where is the
> problem ?
>
> Gunnar
>
> --
>
>
>
>
> Gunnar Brinkmann
> Applied Mathematics and Computer Science
> Ghent University
> Krijgslaan 281 - S9
> B - 9000 Ghent
>
> email: Gunnar.Brinkmann at UGent.be
>
> phone: +32-9-264.48.07, Fax: +32-9-264.49.95
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20060818/c70ba65c/attachment.html