UVictoria Discrete Math Seminar: Gary MacGillivray

An (m, n)-mixed graph consists of a set of vertices, any two of which may be joined by either an edge of one of m colours or an arc of one of n colours, or not be joined at all. The operation of switching at a vertex v of an (m, n)-mixed graph with respect to an element of a subgroup \Gamma of S_m x S_n x S_2 permutes the colours of the edges incident with v, the colours of the arcs incident with v, and the orientation of the arcs incident with v. Switching defines an equivalence relation on the set of all (m, n)-mixed graphs: (m, n)-mixed graphs G and H are \Gamma-switch-equivalent if there exists a sequence of switches that transform G into H.

We consider the following problems and their solutions. For a fixed subgroup \Gamma of S_m x S_n x S_2:

* determine the number of equivalence classes of k vertex (m, n)-mixed graphs under switching with respect to \Gamma.
* how hard is it to determine whether to given (m, n)-mixed graphs G and H are \Gamma-switch equivalent?
* for a fixed (m, n)-mixed graph H, how hard is it to determine whether a given (m, n)-mixed graph G can be switched with respect to \Gamma so that there is a homomorphism of the transformed (m, n)-mixed graph G’ to H? (A homomorphism is a mapping of V(G) to V(H) that preserves edges, arcs and colours.)