1
$\begingroup$

An oriented simple graph is a graph with at most edge between each pair of vertices and where each edge has an orientation. Equivalently, it is a directed graph with at most one edge (of either orientation) between each pair of vertices. In contrast, the definition of a simple directed graph appears to allow at most one of each orientation.

Is isomorphism testing for oriented simple graphs GI-hard? Is there any discussion of the problem in the literature (perhaps using a different name for this class of graphs)?

A tournament has exactly one edge (of either orientation); isomorphism testing for tournaments appears to be open, but has at least been studied [1].

[1] https://link.springer.com/chapter/10.1007/978-3-540-74456-6_51

New contributor
John P. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

1 Answer 1

1
$\begingroup$

I found a previous answer that covers this, by showing that DAG isomorphism is GI-complete: Is DAG isomorphism NP-C

New contributor
John P. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.