Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implementing generators for some small graphs/ digraphs #38320

Open
1 task done
janmenjayap opened this issue Jul 1, 2024 · 4 comments · May be fixed by #38321
Open
1 task done

Implementing generators for some small graphs/ digraphs #38320

janmenjayap opened this issue Jul 1, 2024 · 4 comments · May be fixed by #38321
Labels
c: graph theory

Comments

@janmenjayap
Copy link
Contributor

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 graph2

bicorn-tricorn

  • Murty graph1

Murty-graph

  • KohTindell digraph2

KohTindellDiGraph

  • Cubeplex graph and Twinplex graph3

Cubeplex-Twinplex

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?

  • 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.
@janmenjayap janmenjayap changed the title Implementing generators for graphs/ digraphs Implementing generators for some small graphs/ digraphs Jul 1, 2024
@janmenjayap janmenjayap linked a pull request Jul 1, 2024 that will close this issue
Open
5 tasks
@dcoudert
Copy link
Contributor

dcoudert commented Jul 1, 2024

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
Copy link
Contributor Author

janmenjayap commented Jul 1, 2024 •
edited
Loading

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
Copy link
Contributor

dcoudert commented Jul 1, 2024

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
Copy link
Contributor Author

Sure. Will do that. 😊👍

vbraun pushed a commit to vbraun/sage that referenced this issue Aug 27, 2024
sagemathgh-38321: Implemented generators for some small graphs/ digraphs
a4245db 
    
<!-- ^ Please provide a concise and informative title. -->
This PR adds generators for the Bicorn graph, the Tricorn graph, the
Murty graph, the KohTindell digraph, the Cubeplex Graph and the Twinplex
graph.
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
This PR introduces new static methods, specifically `BicornGraph`,
`TricornGraph`, `MurtyGraph`, `KohTindellDiGraph`, `CubeplexGraph` and
`TwinplexGraph`.
<!-- v Why is this change required? What problem does it solve? -->
There is no current implementation of the generators for the above
mentioned graphs/ digraphs.
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->
Fixes sagemath#38320.


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
Nothing as of now (up to my knowledge).
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->

cc: @dcoudert.
    
URL: sagemath#38321
Reported by: Janmenjaya Panda
Reviewer(s): David Coudert, Janmenjaya Panda
vbraun pushed a commit to vbraun/sage that referenced this issue Sep 19, 2024
sagemathgh-38321: Implemented generators for some small graphs/ digraphs
18e499f 
    
<!-- ^ Please provide a concise and informative title. -->
This PR adds generators for the Bicorn graph, the Tricorn graph, the
Murty graph, the KohTindell digraph, the Cubeplex Graph and the Twinplex
graph.
<!-- ^ Don't put issue numbers in the title, do this in the PR
description below. -->
<!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method
to calculate 1 + 2". -->
<!-- v Describe your changes below in detail. -->
This PR introduces new static methods, specifically `BicornGraph`,
`TricornGraph`, `MurtyGraph`, `KohTindellDiGraph`, `CubeplexGraph` and
`TwinplexGraph`.
<!-- v Why is this change required? What problem does it solve? -->
There is no current implementation of the generators for the above
mentioned graphs/ digraphs.
<!-- v If this PR resolves an open issue, please link to it here. For
example, "Fixes sagemath#12345". -->
Fixes sagemath#38320.


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
Nothing as of now (up to my knowledge).
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->

cc: @dcoudert.
    
URL: sagemath#38321
Reported by: Janmenjaya Panda
Reviewer(s): David Coudert, Janmenjaya Panda
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Implemented generators for some small graphs/ digraphs janmenjayap/sage
2 participants
@dcoudert @janmenjayap