zbMATH — the first resource for mathematics

On the genus of the tensor product of graphs where one factor is a regular graph. (English) Zbl 0812.05019
Authors’ 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\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[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.