[Nauty-list] weighted graph questions

[Brendan McKay]

For some reason Slava's mail didn't reach me.

Greg's answer to question (1) is good.  Although several people have implemented this method for their own applications, I don't know of any general purpose code available.  Probably there should be.

Regarding (2), nothing is published but I'll give you the general idea.  The input is a
simple graph G.  First the automorphism group A of G is computed.  Then a list of
possible edge weightings is generated, and those weightings are output if they
are lexicographically minimal under A.  That is, a weighting w is output if there
is no automorphism a in A such that a(w) is lexicographically less than w.
The implementation is not good when the group is very large.

Brendan.

From: Gregory Puleo <gpuleo at gmail.com<mailto:gpuleo at gmail.com>>
Date: Monday, 12 August 2013 1:38 AM
To: Vyacheslav Rychkov <vyacheslav.rychkov at cern.ch<mailto:vyacheslav.rychkov at cern.ch>>
Cc: "nauty-list at cs.anu.edu.au<mailto:nauty-list at cs.anu.edu.au>" <nauty-list at cs.anu.edu.au<mailto:nauty-list at cs.anu.edu.au>>
Subject: Re: [Nauty-list] weighted graph questions

For (1), you can treat the edge weights like edge colors and use the technique described for edge coloring in the Nauty User's Guide (use multiple "layers" of edges to represent the binary expansion of the edge color).

I don't know anything about (2).

-Greg


On Sun, Aug 11, 2013 at 2:23 AM, Vyacheslav Rychkov <vyacheslav.rychkov at cern.ch<mailto:vyacheslav.rychkov at cern.ch>> wrote:
Dear nauty-users,

I have two questions related to the use of nauty for weighted graphs.

1) I am looking for a code which computes the automorphism group of a weighted graph (i.e. with weights assigned to edges).
I have only integer edge weights, no vertex coloring, and relatively small graphs (connected graphs with O(10) edges).

It seems that nauty cannot compute the automorphism group of a weighted graph.
Can anyone point me to a publicly available code which does that?

2) Inside the nauty distribution, there is a multig utility which produces a list of nonisomorphic multigraphs out of a list of nonisomorphic simple graphs,
increasing mutliplicities of edges in all possible ways. Is there a place where the algorithm is described?

Any help would be greatly appreciated,
Kind regards,
Slava Rychkov

--
Vyacheslav Rychkov
Staff, CERN Theory Division
vyacheslav.rychkov at cern.ch<mailto:vyacheslav.rychkov at cern.ch>
http://sites.google.com/site/slavarychkov/
Office 4-2.070
+(41-22-76)74141<tel:%2B%2841-22-76%2974141> (off)
+33(0)649884087<tel:%2B33%280%29649884087> (mob)
+41-22-7673850<tel:%2B41-22-7673850> (fax)
Mailing adress: PH-TH, Case C01600, CERN, CH-1211 Geneva 23



_______________________________________________
Nauty-list mailing list
Nauty-list at cs.anu.edu.au<mailto:Nauty-list at cs.anu.edu.au>
http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list




--
Gregory Puleo
http://www.math.uiuc.edu/~puleo/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20130812/0290213e/attachment.html