Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The genera of amalgamations of graphs


Author: Seth R. Alpert
Journal: Trans. Amer. Math. Soc. 178 (1973), 1-39
MSC: Primary 05C10
DOI: https://doi.org/10.1090/S0002-9947-1973-0371698-X
MathSciNet review: 0371698
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: If $ p \leq m$, n then $ {K_m}{ \vee _{{K_p}}}{K_n}$ is the graph obtained by identify ing a copy of $ {K_p}$ contained in $ {K_m}$ with a copy of $ {K_p}$ contained in $ {K_n}$ . It is shown that for all integers $ p \leq m$, n the genus $ g({K_m}{ \vee _{{K_p}}}{K_n})$ of $ {K_m}{ \vee _{{K_p}}}{K_n}$ is less than or equal to $ g({K_m}) + g({K_n})$. Combining this fact with the lower bound obtained from the Euler formula, one sees that for $ 2 \leq p \leq 5,g({K_m}{ \vee _{{K_p}}}{K_n})$ is either $ g({K_m}) + g({K_n})$ or else $ g({K_m}) + g({K_n}) - 1$. Except in a few special cases, it is determined which of these values is actually attained.


References [Enhancements On Off] (What's this?)

  • [1] J. Battle, F. Harary, Y. Kodama and J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962), 565-568. MR 27 #5247. MR 0155313 (27:5247)
  • [2] J. Ch. Boland, Embedding of graphs into orientable surfaces, Nederl. Akad. Wetensch. Proc. Ser. A 70 = Indag. Math. 29 (1967), 33-44. MR 35 #2272. MR 0211391 (35:2272)
  • [3] J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), 646. Abstract #572-1.
  • [4] W. Gustin, Orientable imbedding of Cayley graphs, Bull. Amer. Math. Soc. 69 (1963), 272-275. MR 26 #3037. MR 0145506 (26:3037)
  • [5] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [6] I. N. Kagno, The mapping of graphs on surfaces, J. Math. and Phys. 16 (1937), 46-75.
  • [7] J. Mayer, Le problème des régions voisines sur les surfaces closes orientables, J. Combinatorial Theory 6 (1969), 177-195. MR 38 #3177. MR 0234863 (38:3177)
  • [8] G. Ringel, Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, 2, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959. MR 22 #235. MR 0109349 (22:235)
  • [9] G. Ringel and J. W. T. Youngs, Lösung des Problems der Nachbargebiete, Arch. Math. (Basel) 20 (1969), 190-201. MR 39 #4049. MR 0242720 (39:4049)
  • [10] -, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U. S. A. 60 (1968), 438-445. MR 37 #3959. MR 0228378 (37:3959)
  • [11] -, Solution of the Heawood map-coloring problem--case 11, J. Combinatorial Theory 7 (1969), 71-93. MR 39 #1360. MR 0240006 (39:1360)
  • [12] -, Solution of the Heawood map-coloring problem--case 2, J. Combinatorial Theory 7 (1969), 342-352. MR 42 #128. MR 0265216 (42:128)
  • [13] -, Solution of the Heawood map-coloring problem--case 8, J. Combinatorial Theory 7 (1969), 353-363. MR 41 #6723. MR 0262113 (41:6723)
  • [14] C. M. Terry, L. R. Welch and J. W. T. Youngs, The genus of $ {K_{12s}}$, J. Combinatorial Theory 2 (1967), 43-60. MR 34 #6755. MR 0206939 (34:6755)
  • [15] -, Solution of the Heawood map-coloring problem--case 4, J. Combinatorial Theory 8 (1970), 170-174. MR 41 #3321. MR 0258675 (41:3321)
  • [16] J. W. T. Youngs, The Heawood map coloring conjecture, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 313-354. MR 38 #4357. MR 0236059 (38:4357)
  • [17] -, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303-315. MR 26 #3043. MR 0145512 (26:3043)
  • [18] J. W. T. Youngs, Solution of the Heawood map-coloring problem--cases 3, 5, 6, and 9, J. Combinatorial Theory 8 (1970), 175-219. MR 41 #3322. MR 0258676 (41:3322)
  • [19] -, Solution of the Heawood map-coloring problem--cases 1, 7, and 10, J. Combinatorial Theory 8 (1970), 220-231. MR 41 #3323. MR 0258677 (41:3323)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C10

Retrieve articles in all journals with MSC: 05C10


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1973-0371698-X
Keywords: Orientable 2-manifold, genus, Euler formula, Complete Graph Theorem
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society