[Nauty] generate signed graphs

[Edel Sherratt [eds] (Staff)]

Hello nauty community,
About 20 years ago I used nauty for something similar in Chemistry, where I wanted to generate distinct molecules , represented as graphs with edge and vertex colouring.  The edge colouring represented the kind of bond, and the vertex colouring the kind of atom in question.
Anyway, while nauty gave me a way to generate non-isomorphic vertex-labelled graphs, I also needed a way to deal with edges.  To persuade nauty to deal with edges. I worked with graphs whose vertices consisted of two nodes and an edge.
The same  technique might apply to the problem with signed graphs.
Here are some slides I used in 2014 to explain the technique.  I also have some software, written in a mixture of Haskell and C.  If you would like that, I can update it to run using current Haskell.
Best regards,
Edel


________________________________
From: Nauty <nauty-bounces at anu.edu.au> on behalf of lczhangmath via Nauty <nauty at anu.edu.au>
Sent: 15 December 2023 03:00
To: nauty at anu.edu.au <nauty at anu.edu.au>
Subject: [Nauty] generate signed graphs

[You don't often get email from nauty at anu.edu.au. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]

[RHYBUDD! E-BOST ALLANOL / CAUTION! EXTERNAL E-MAIL]


A signed graph is a graph in which each edge has a plus or minus sign. Two signed graphs are isomorphic if their underlying graphs are isomorphic through a mapping under which signs of edges are preserved.


Given an underlying graph G, to obtain all non-isomorphic directed graphs, I know that nauty has the directg function. Similarly, for signed graphs, is it possible to design a similar function to obtain all non-isomorphic signed graphs with G as the underlying graph?


PS: I haven't found tools for generating (connected) signed graphs with n vertices either. So I posted a corresponding question on MathOverflow; see https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmathoverflow.net%2Fquestions%2F460413%2Fgenerate-all-non-isomorphic-signed-graphs&data=05%7C02%7C%7Cf40c350b6097485250f008dbfd1a987c%7Cd47b090e3f5a4ca084d09f89d269f175%7C0%7C0%7C638382062917892650%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=fdjdFkbn%2FcdvJvkVr2TVZLMCKXLjKw28K%2FpRgMvCq%2Fw%3D&reserved=0<https://mathoverflow.net/questions/460413/generate-all-non-isomorphic-signed-graphs>.
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailman.anu.edu.au%2Fmailman%2Flistinfo%2Fnauty&data=05%7C02%7C%7Cf40c350b6097485250f008dbfd1a987c%7Cd47b090e3f5a4ca084d09f89d269f175%7C0%7C0%7C638382062917892650%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=b1ea0Yq4v6xxdHoLG6rbaSdMXIyBeKFsxMCpf0QxJyQ%3D&reserved=0<https://mailman.anu.edu.au/mailman/listinfo/nauty>


----------------------------------------------------------------------------------------------------------------------
Y Brifysgol orau yn y DU am Ansawdd ei Dysgu a Phrofiad Myfyrwyr
Best University in the UK for Teaching Quality and Student Experience
(The Times and Sunday Times, Good University Guide 2021)
Rydym yn croesawu gohebiaeth yn Gymraeg a Saesneg. Cewch ateb Cymraeg i bob gohebiaeth Gymraeg ac ateb Saesneg i bob gohebiaeth Saesneg. Ni fydd gohebu yn Gymraeg yn arwain at oedi.
We welcome correspondence in Welsh and English. Correspondence received in Welsh will be answered in Welsh and correspondence in English will be answered in English. Corresponding in Welsh will not involve any delay.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: GCM2014.pptx
Type: application/vnd.openxmlformats-officedocument.presentationml.presentation
Size: 461638 bytes
Desc: GCM2014.pptx
URL: <https://mailman.anu.edu.au/pipermail/nauty/attachments/20231215/48e37847/attachment-0001.pptx>