On the genus of the tensor product of graphs where one factor is a regular graph.

*(English)*Zbl 0812.05019Authors’ abstract: The tensor product \(H\otimes G\) where \(G\) is a \(2k\)- regular graph can be regarded as a covering space of the permutation voltage graph \(H^{(2k)}\) obtained from \(H\). Assuming that \(H\) is suitably imbedded in some orientable surface by modifying the edges of \(H\) according to the configuration of \(G\) we get the permutation voltage graph \(H^{(2k)}\) whose permutation derived graph is exactly \(H\otimes G\). This construction can also be extended to the tensor product \(H\otimes G\) where \(G\) is a \((2k+ 1)\)-regular graph with 1-factor. Here we put the sufficient conditions on \(H\) and \(G\) so that the permutation derived imbedding obtained in this way is a minimal imbedding. We also give sample results—the genus of the tensor products \(H\otimes K_{2n,2n}\) and \(H\otimes Q_ n\) are calculated for certain graphs \(H\).

Reviewer: B.Mohar (Ljubljana)

##### MSC:

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

##### Keywords:

2-cell embedding; regular graph; tensor product; permutation voltage graph; orientable surface; 1-factor; imbedding; genus
PDF
BibTeX
XML
Cite

\textit{T. Dakić} and \textit{T. Pisanski}, Discrete Math. 134, No. 1--3, 25--39 (1994; Zbl 0812.05019)

Full Text:
DOI

**OpenURL**

##### References:

[1] | G. Abay-Asmerom, On genus imbeddings of the tensor product of graphs, to appear. · Zbl 0860.05025 |

[2] | () |

[3] | Bouchet, A.; Mohar, B., Triangular embeddings of tensor products of graphs, (), 129-135 · Zbl 0697.05025 |

[4] | Garman, B.L.; Ringeisen, R.D.; White, A.T., On the genus of strong tensor products of graphs, Canada. J. math., 28, 523-532, (1976), No. 3 · Zbl 0336.05103 |

[5] | Gross, J.L.; Tucker, T.W., Topological graph theory, (1987), Wiley New York · Zbl 0621.05013 |

[6] | Harary, F.; Wilcox, G.W., Boolean operat. on graphs math. scand., 20, 41-51, (1967) · Zbl 0152.22801 |

[7] | Mohar, B.; Pisanski, T.; White, A.T., Genus of Cartesian products of nearly bipartite graphs, J. graph theory, 13, 301-310, (1990) · Zbl 0729.05014 |

[8] | Pisanski, T., Genus of Cartesian products of regular bipartite graphs, J. graph theory, 4, 41-51, (1980) |

[9] | Weichesel, P.M., The Kronecker product of graphs, Proc. amer. math. soc., 13, 47-52, (1962) · Zbl 0102.38801 |

[10] | White, A.T., Graphs, groups and surfaces, (1984), North-Holland Amsterdam · Zbl 0378.05028 |

[11] | White, A.T., Covering graphs and graphical products, (), 239-247 |

[12] | Z̆eleznik, V., Quadrilateral embeddings of the conjunction of graphs, Math. slovaca, 38, 89-98, (1988) · Zbl 0654.05025 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.