Message Boards Message Boards

0
|
6463 Views
|
2 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Canonical graph

Posted 9 years ago

Hello

I'm wanting to find out what the definition of canonical graph labelling is for the canonicalgraph function in mathematica. Any ideas where I can get that information? All I can see in the description is that it puts the graph in a canonical form, but no indication on what that form is e.g. Maximising or minimising sequences from the adjacency matrix etc.

Cheers

POSTED BY: Stuart Marshall
2 Replies

For the intended application, it does not matter. What is important is that g1 and g2 are isomorphic if and only if CanonicalGraph[g1] === CanonicalGraph[g2].

There are many different ways to define (and compute) a canonical form with this property. All of them are complicated. For example, the Bliss library (which you can access in Mathematica through IGraph/M) provides multiple such forms.

POSTED BY: Szabolcs Horvát

Graph canonization is a NP-hard computational problem. A discussion of canonical graphs is given, for example, in

http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

POSTED BY: S M Blinder
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract