zbMATH — the first resource for mathematics

Quadrilateral embeddings of the conjunction of graphs. (English) Zbl 0654.05025
Let \(G=(V,E)\) be a connected bipartite graph with bipartition \(V=V_1\cup V_2\), and suppose \(G\) admits a quadrilateral embedding \(i\colon G\to S\) in some closed surface \(S\). The embedding \(i\) is said to be diagonalizable if there exists a graph \(G'=(V,E')\) with an embedding \(j\colon G'\to S\) and a 1-factor \(F\) in \(G'\) such that (a) every edge in \(F\) has both endvertices either in \(V_1\) or else in \(V_2\), (b) \(G'-F=G\), and (c) \(j\) restricted to \(G\) is equal to \(i\).
The main result of the paper is that if a bipartite graph \(G\) has a diagonalizable quadrilateral embedding, then the categorical product of \(G\) with an arbitrary graph has an embedding of the same type. This is then applied to determining orientable and non-orientable genera of several classes of graphs.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML
[1] BATTLE J., HARARY F., KODAMA Y., YOUNGS J. W. T.: Additivity of the genus of a graph. Bull. Amer. Math. Soc. 68, 1962, 565-568. · Zbl 0142.41501
[2] BEINEKE L. W., HARARY F.: The genus of the n-cube. Canad. J. Math. 17, 1965, 494-496. · Zbl 0127.13801
[3] FARSAN M., WALLER D. A.: Kronecker products and local joins of graphs. Canad. J. Math. 29, 1977, 255-269. · Zbl 0343.18004
[4] HARARY F.: Graph Theory. Addison-Wesley, Reading, Mass. 1969. · Zbl 0196.27202
[5] JUNGERMAN M.: The non-orientable genus of the n-cube. Pacific. J. Math 76, 1978, 443-451. · Zbl 0386.05026
[6] RINGEL G.: Das Geschlecht des vollständigen paaren Graphen. Abh. Math. Sem. Univ. Hamburg 28, 1965, 139-150. · Zbl 0132.21203
[7] RINGEL G.: Der vollständige paare Graph auf nichtorientierbaren Flächen. J. Reine Angew. Math. 220, 1965, 88-93. · Zbl 0132.21204
[8] STAHL S.: Generalized embedding schemes. J. Graph Theory 2, 1978, 41-52. · Zbl 0396.05013
[9] WEICHSEL P. M.: The Kronecker product of graphs. Proc. Amer. Math. Soc. 13, 1962, 47-52. · Zbl 0102.38801
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.