On the Graph Isomorphism Completeness of Directed and Multidirected Graphs

Sebastian Pardo-Guerra (), Vivek Kurien George and Gabriel A. Silva
Additional contact information
Sebastian Pardo-Guerra: Center for Engineered Natural Intelligence, La Jolla, CA 92093, USA
Vivek Kurien George: Lawrence Livermore National Laboratory, Livermore, CA 94550, USA
Gabriel A. Silva: Center for Engineered Natural Intelligence, La Jolla, CA 92093, USA

Mathematics, 2025, vol. 13, issue 2, 1-16

Abstract: 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.

Keywords: directed graphs; undirected graphs; graph isomorphism completeness; category theory (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/2/228/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/2/228/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:2:p:228-:d:1564742

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().