On the Graph Isomorphism Completeness of Directed and Multidirected Graphs
The category of directed graphs is isomorphic to a particular category whose objects are labeled undirected bipartite graphs and whose morphisms are undirected graph morphisms that respect the labeling. Based on this isomorphism, we begin by showing that the class of all directed graphs is a Graph I...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/2/228 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588045176537088 |
|---|---|
| author | Sebastian Pardo-Guerra Vivek Kurien George Gabriel A. Silva |
| author_facet | Sebastian Pardo-Guerra Vivek Kurien George Gabriel A. Silva |
| author_sort | Sebastian Pardo-Guerra |
| collection | DOAJ |
| description | The category of directed graphs is isomorphic to a particular category whose objects are labeled undirected bipartite graphs and whose morphisms are undirected graph morphisms that respect the labeling. Based on this isomorphism, we begin by showing that the class of all directed graphs is a Graph Isomorphism Complete class. Afterwards, by extending this categorical framework to weighted prime graphs, we prove that the categories of multidirected graphs with and without self-loops are each isomorphic to a particular category of weighted prime graphs. Consequently, we prove that these classes of multidirected graphs are also Graph Isomorphism Complete. |
| format | Article |
| id | doaj-art-26d6a4de840e4f4e974b407af94c7cb2 |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-26d6a4de840e4f4e974b407af94c7cb22025-01-24T13:39:49ZengMDPI AGMathematics2227-73902025-01-0113222810.3390/math13020228On the Graph Isomorphism Completeness of Directed and Multidirected GraphsSebastian Pardo-Guerra0Vivek Kurien George1Gabriel A. Silva2Center for Engineered Natural Intelligence, La Jolla, CA 92093, USALawrence Livermore National Laboratory, Livermore, CA 94550, USACenter for Engineered Natural Intelligence, La Jolla, CA 92093, USAThe category of directed graphs is isomorphic to a particular category whose objects are labeled undirected bipartite graphs and whose morphisms are undirected graph morphisms that respect the labeling. Based on this isomorphism, we begin by showing that the class of all directed graphs is a Graph Isomorphism Complete class. Afterwards, by extending this categorical framework to weighted prime graphs, we prove that the categories of multidirected graphs with and without self-loops are each isomorphic to a particular category of weighted prime graphs. Consequently, we prove that these classes of multidirected graphs are also Graph Isomorphism Complete.https://www.mdpi.com/2227-7390/13/2/228directed graphsundirected graphsgraph isomorphism completenesscategory theory |
| spellingShingle | Sebastian Pardo-Guerra Vivek Kurien George Gabriel A. Silva On the Graph Isomorphism Completeness of Directed and Multidirected Graphs Mathematics directed graphs undirected graphs graph isomorphism completeness category theory |
| title | On the Graph Isomorphism Completeness of Directed and Multidirected Graphs |
| title_full | On the Graph Isomorphism Completeness of Directed and Multidirected Graphs |
| title_fullStr | On the Graph Isomorphism Completeness of Directed and Multidirected Graphs |
| title_full_unstemmed | On the Graph Isomorphism Completeness of Directed and Multidirected Graphs |
| title_short | On the Graph Isomorphism Completeness of Directed and Multidirected Graphs |
| title_sort | on the graph isomorphism completeness of directed and multidirected graphs |
| topic | directed graphs undirected graphs graph isomorphism completeness category theory |
| url | https://www.mdpi.com/2227-7390/13/2/228 |
| work_keys_str_mv | AT sebastianpardoguerra onthegraphisomorphismcompletenessofdirectedandmultidirectedgraphs AT vivekkuriengeorge onthegraphisomorphismcompletenessofdirectedandmultidirectedgraphs AT gabrielasilva onthegraphisomorphismcompletenessofdirectedandmultidirectedgraphs |