Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-16T15:04:23.211Z Has data issue: false hasContentIssue false
  • English
  • Français

The Maximum Genus of Cartesian Products of Graphs

Published online by Cambridge University Press:  20 November 2018

Joseph Zaks
Joseph Zaks*
Affiliation:
Michigan State University, East Lansing, Michigan; University of Haifa, Haifa, Israel
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The maximum genus γM(G) of a connected graph G has been defined in [2] as the maximum g for which there exists an embedding h : G —> S(g), where S(g) is a compact orientable 2-manifold of genus g, such that each one of the connected components of S(g) — h(G) is homeomorphic to an open disk; such an embedding is called cellular. If G is cellularly embedded in S(g), having V vertices, E edges and F faces, then by Euler's formula

V-E + F = 2-2g.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 26 , Issue 5 , October 1974 , pp. 1025 - 1035
Copyright
Copyright © Canadian Mathematical Society 1974

References

1. Duke, R., The genus, regional number, and the Betti number of a graph, Can. J. Math. 18 (1966), 817–822.Google Scholar
2. Nordhaus, E. A., Stewart, B. M., and White, A. T., On the maximum genus of a graph, J. Combinatorial Theory Ser. B 11 (1971), 258–267.Google Scholar
3. Nordhaus, E. A., Ringeisen, R. D., Stewart, B. M., and White, A. T., A Kuratowski-type theorem for the maximum genus of a graph, J. Combinatorial Theory Ser. B 12 (1972), 260–267.Google Scholar
4. Ringeisen, R. D., Determining all compact orientable 2-manifolds upon which Kmtn has 2-cell imbeddings, J. Combinatorial Theory Ser. B 12 (1972) 101–104.Google Scholar
5. Ringeisen, R. D., Upper and lower imbeddable graphs, Graph theory and applications (Y. Alavi, et al.» editors), Springer-Verlag, Vol. 303, 1972 6. G. Sabidussi, Graph multiplication, Math. Z. 72 (1960), 446–457.Google Scholar
7. Tutte, W. T., The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111.Google Scholar
8. White, A. T., The genus of the Cartesian product of two graphs, J. Combinatorial Theory Ser. B 11 (1971), 89–94.Google Scholar
9. White, A. T., On the genus of products of graphs, Recent Trends in Graph Theory (M. Capobianco, et al., editors), Springer-Verlag, Vol. 186, 1971.Google Scholar
10. Zaks, J., On the 1-factors of n-connected graphs, J. Combinatorial Theory Ser. B 11 (1971), 169–180.Google Scholar