Implementing generators for some small graphs/ digraphs

[janmenjayap]

Problem Description

Currently, there are no existing implementation of the generators for the following graphs/ digraphs:

• Bicorn graph
• Tricorn graph
• Murty graph
• KohTindell digraph
• Cubeplex graph
• Twinplex graph

Proposed Solution

We shall follow the generators for the graphs as explained below.

1. The definitions/ generators go as follows:

• Bicorn graph and Tricorn graph²

• Murty graph¹

• KohTindell digraph²

• Cubeplex graph and Twinplex graph³

Alternatives Considered

Their might be different embeddings possible for each individual graph/ digraph mentioned.

Additional Information

This implementation is a part of the project: link.

cc: @dcoudert.

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

---

References

1. Marcelo H. de Carvalho, Nishad Kothari, Xiumei Wang and Yixun Linc. Birkhoff–von Neumann graphs that are PM-compact. 2019. arXiv: abs/1807.07339.
2. C.L. Lucchesi, U.S.R. Murty. Perfect Matchings: A Theory of Matching Covered Graphs. Algorithms and Computation in Mathematics. Springer Cham, 1st edition, 2024. doi: 10.1007/978-3-031-47504-7.
3. Serguei Norine and Robin Thomas. Minimally Non-Pfaffian Graphs. Combinatorica, vol. 27, no. 5, pages: 587 -- 600, Springer. 2007. doi: 10.1016/j.jctb.2007.12.005.

[dcoudert]

Have you checked that these graphs are not already available under a different name ? For instance, the Koh-Tindell digraph is digraphs,Circulant(7, [1, 5]).

[janmenjayap]

The Bicorn graph is graphs.StaircaseGraph(4). Up to my knowledge, there is no implementation of the other four graphs. I might be wrong.

These are like specific graphs. For example, graphs.WagnerGraph() is essentially graphs.MoebiusLadderGraph(4) or graphs.CirculantGraph(8, [1, 4]), but since it is a named graph, I suppose it demands a separate implementation.

Actually, I meant the named implementation. Sorry for the confusion.

[dcoudert]

For some graphs, for instance for the Koh-Tindell digraph, it might be enough to add the documentation of circulant digraph that when parameters are (7, [1, 5]), the digraph is also known as the Koh-Tindell digraph ?

I'm not against adding named (di)graphs but we can avoid adding lot's of code for graph that can be obtained from a family.

[janmenjayap]

Sure. Will do that. 😊👍