Isomorphism for Digraphs and Sequences of Shop Scheduling Problems

The computational complexity of the graph isomorphism problem is still unknown. We consider Cartesian products \(K_n \times K_m\) of two complete graphs \(K_n\) and \(K_m\). An acyclic orientation of such a Cartesian product is called a sequence graph because it has an application in production scheduling. It can be shown that the graph isomorphism problem on the class of these acyclic digraphs is solvable in polynomial time. We give numbers of non-isomorphic sequence graphs for small \(n\) and \(m\). The orientation on the cliques of a sequence graph can be interpreted as job orders and machine orders of a shop scheduling problem with a complete operation set.