3
$\begingroup$

Brendan McKay's webpage lists all possible $40$-node strongly regular graphs. Is there a standard way to name them uniquely?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This may not be exactly what you had in mind, but in the context of displaying information on web pages, there is a need for a canonical labelling of graph isomorphism classes.

The proposed web standard is here. As is typical with these things, the standards are debated for some years before they may be accepted, but this one seems relatively stable. Code for evaluating it (which also allows you to examine the implementation of the algorithm) is here. In terms of a "standard way" of naming these things, this is about as standard as you can get.

The graph isomorphism portion of the RDF specification is an attempt to answer your question (for any graph). Since we're considering 40-node strongly regular graphs and there's only 28 of them, you could also encode them in some fashion and sort lexicographically. But both these approaches may fail on aesthetic grounds-- maybe we'd really like to describe some relationship between the isomorphism classes that characterizes them in a mathematically meaningful way. Perhaps that's the real question?

Improve this answer
$\endgroup$
2
  • $\begingroup$ I tried to read those documents, but I literally cannot find an actual graph isomorphism / canonicalisation procedure in there. It talks about issuers, and quads, and blank nodes and Hash N-degree quads, and lots of acronyms that lead to other things I don't understand. But I couldn't see anything that I could recognise as graph isomorphism? $\endgroup$
    – Gordon Royle
    Commented Aug 15, 2021 at 3:58
  • $\begingroup$ @GordonRoyle , I am extremely sympathetic to your reaction to the teeth-gritting opacity of the language. As for the GI connection, just search for the phrase "graph isomorphism problem". For a possibly clearer explanation, check out Section 1.2.1 here: w3c.github.io/lds-wg-charter/explainer.html#generalProblem , especially the Arnold/Longley paper. (Full disclosure: I'm part of the "Mirabolic Consulting" that gets mentioned in passing.) $\endgroup$
    – Bill Bradley
    Commented Aug 15, 2021 at 12:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .