Imbeddings of the tensor product of graphs where the second factor is a complete graph Original Research Article

In this paper we present genus result for the tensor product of graphs where the second factor is the complete graph Km and m is a power of 2. We are going to view the second factor as a Cayley graph and we will use an imbedding technique that combines surgery and voltage graph theory. In this imbedding technique we start with a suitable imbedding of H on some surface and then modify the edges of H according to the nature of Km to get a voltage graph H∗. The covering graph of this voltage graph H∗ will be the desired tensor product of H with Km. The genus of H ⊗ Km, where H is a graph with a quadrilateral imbedding and also H is either, bipartite, with bichromatic dual, or with straight-ahead imbedding is given